P4559:「JSOI2018」列队 – 题解

主要思路

一开始想了一个假的，后面写完了之后才意识到哪里错了，就很傻逼。

首先贪心的知道，肯定是第 \(i\) 小的数位于 \(K + i – 1\) 的位置上。我们算答案的时候会发现无非就是把贡献根据绝对值的拆法进行分开处理，一部分是 \((a_i – rk_i) – (k – 1)\)，还有一部分是 \((k – 1) – (a_i – rk_i)\)。所以我们需要一个数据结构来拆分这两个部分。

首先我们知道这两个部分肯定是连续的两段，因为前后的 Delta 都至多为 \(1\)。知道这个性质之后，我们其实可以尝试用主席树来搞区间内的段。考虑用势能线段树的那一套，我们可以把段一直下传，直到段完整为止。

对于完整的段，发现其实就是给上面那个贡献式子套 \(\sum\)，而且发现套 \(\sum\) 的时候要记录这一段和的左端点，这样就可以用等差数列直接搞了。

代码

// P4559.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200, RANGE = 1e6;

typedef long long ll;

int n, m, ai[MAX_N], roots[MAX_N], ptot;

struct node
{
    int val, lson, rson;
    ll sum;
} nodes[MAX_N * 30];

#define mid ((l + r) >> 1)

int update(int qx, int l, int r, int pre)
{
    int p = ++ptot;
    nodes[p] = nodes[pre], nodes[p].val++, nodes[p].sum += qx;
    if (l == r)
        return p;
    if (qx <= mid)
        nodes[p].lson = update(qx, l, mid, nodes[pre].lson);
    else
        nodes[p].rson = update(qx, mid + 1, r, nodes[pre].rson);
    return p;
}

ll query(int l, int r, int p, int pre, int cur, int k)
{
    if (nodes[p].val - nodes[pre].val == 0)
        return 0;
    int siz = nodes[p].val - nodes[pre].val;
    ll sum = nodes[p].sum - nodes[pre].sum;
    if (k + cur <= l)
        return sum - 1LL * ((k + cur) + (k + cur + siz - 1)) * siz / 2;
    else if (r <= k + cur + siz - 1)
        return 1LL * ((k + cur) + (k + cur + siz - 1)) * siz / 2 - sum;
    int lsiz = nodes[nodes[p].lson].val - nodes[nodes[pre].lson].val;
    return query(l, mid, nodes[p].lson, nodes[pre].lson, cur, k) +
           query(mid + 1, r, nodes[p].rson, nodes[pre].rson, cur + lsiz, k);
}

#undef mid

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]), roots[i] = update(ai[i], 1, RANGE, roots[i - 1]);
    while (m--)
    {
        int L, R, k;
        scanf("%d%d%d", &L, &R, &k);
        printf("%lld\n", query(1, RANGE, roots[R], roots[L - 1], 0, k));
    }
    return 0;
}