P3332 [ZJOI2013] K大数查询

· · 题解

有一种经典的权值线段树套区间线段树的做法。

对于外层权值线段树，将一个数加入进线段树时对相对应的内层线段树区间加 1。

查询第 k 大数可以外层权值线段树上对内层区间数值个数二分。

那么看到这个做法，我不禁想到可不可以把权值线段树换成权值树状数组。

答案是肯定的。

插入显然。但是我们似乎不知道如何查询第 k 大。

对于权值树状数组，我们可以用如下代码实现查询区间第 k 小数。

int GetKthSmallest(const int &k) {
    int reply = 0, cnt = 0;
    for (int i = 17; i >= 0; --i) 
        reply += (1 << i), reply > *num || cnt + c[reply] >= k ? reply -= (1 << i) : cnt += c[reply];
    return ++reply;
}

这段代码在干嘛？

这就是树状数组二分。即存在某个数 \delta 使得 \forall x\le \delta 都满足该性质（排名小于等于 k），\forall x> \delta 都不满足该性质。

那么怎么实现呢？考虑到权值树状数组是个前缀桶，我们可以用从高位到低位倍增实现，每次尝试把答案 r 加上一个二进制位，若合法且排名小于 k 可以加入该位。注意到加入该位后需要把前面个数计入。最后答案恰好在下一位。

那么我们把上面的代码稍微修改一下就可以树套树搞搞。

但是有个问题：这道题要求查询第 k 大数，怎么办呢？

我们可以离散化（还剩 n' 个数）后对每个数 x 插入 n'-x+1，查询第 k 小得到 x 后返回 n'-x+1 对应数即可。

#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 5e4 + 5, Times = 168;
struct Operation {
    int tp, l, r;
    ll c;
} op[maxn];
int ls[maxn * Times], rs[maxn * Times], len, rt[maxn], n, num[maxn], m;
ll d[maxn * Times], vis[maxn * Times];
void InModify(const int &l, const int &r, const ll &c, int &p, const int &s = 1, const int &t = n) {
    p || (p = ++len), d[p] += (min(r, t) - max(l, s) + 1) * c;
    if (l <= s && t <= r) return void(vis[p] += c);
    int mid = s + ((t - s) >> 1);
    if (l <= mid) InModify(l, r, c, ls[p], s, mid);
    if (r > mid) InModify(l, r, c, rs[p], mid + 1, t);
}
ll InGet(const int &l, const int &r, const int &p, const int &s = 1, const int &t = n) {
    if (!p) return 0;
    if (l <= s && t <= r) return d[p];
    int mid = s + ((t - s) >> 1);
    ll reply = vis[p] * (min(r, t) - max(l, s) + 1);
    if (l <= mid) reply += InGet(l, r, ls[p], s, mid);
    if (r > mid) reply += InGet(l, r, rs[p], mid + 1, t);
    return reply;
}
inline int lowbit(const int &x) { return x & -x; }
void OutUpdate(int i, const int &l, const int &r) { for (; i <= *num; i += lowbit(i)) InModify(l, r, 1, rt[i]); }
ll OutGetKthSmallest(const ll &k, const int &l, const int &r) {
    ll reply = 0, cnt = 0, x;
    for (int i = 17; ~i; --i)
        reply += (1 << i), reply > *num || cnt + (x = InGet(l, r, rt[reply])) >= k ? reply -= (1 << i) : cnt += x;
    return ++reply;
}

int main() {    
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
        scanf("%d%d%d%lld", &op[i].tp, &op[i].l, &op[i].r, &op[i].c), op[i].tp == 1 && (num[++*num] = op[i].c);
    sort(num + 1, num + *num + 1), *num = unique(num + 1, num + *num + 1) - num - 1;
    for (int i = 1; i <= m; ++i) {
        if (op[i].tp == 1) OutUpdate(*num - (lower_bound(num + 1, num + *num + 1, op[i].c) - num) + 1, op[i].l, op[i].r);
        else printf("%d", num[*num - OutGetKthSmallest(op[i].c, op[i].l, op[i].r) + 1]), putchar(10);
    }
    return 0;
}