题解 P2617 【Dynamic Rankings】

· · 题解

为什么没有分块的题解？？？这道题分块完全跑的过（900 mm）,来发一个分块的题解（逃） （话说分块维护这种动态区间K小不是应当很常见吗……） 分成sqrt（n）块， 块的大小为sqrt（n），块内维护有序数列。 修改就暴力重构块，显然不会超时

对于每一个询问，先二分一个区间权值（发现这道题是1~1e9），然后去统计所求的区间内小于这个数的个数有多少。对于两边不完整的块暴力统计，对于完整的块，则二分查找最小的~~数，即可在log时间内得到答案，请看代码吧

时间复杂度 O(nlog1e9logT \frac{n}{T} +nTlogT)

当T = \sqrt n达到顶尖

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std; 
typedef long long ll;
const int N = 10000;
const int B = 105;
const int Maxn = 1e9;

int n, m, bnum;
ll a[N + 5], an[N + 5], pos[N + 5], l[B], r[B];

template <typename T>
inline void read(T &X) {
    X = 0;
    char ch = 0;
    T op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op; 
}

inline void modify(int x, ll c) {
    a[x] = c;
    for(int i = l[pos[x]]; i <= r[pos[x]]; i++)
        an[i] = a[i];
    sort(an + l[pos[x]], an + r[pos[x]] + 1);
}

inline ll getNum(int b, ll v) {
    ll ln = l[b], rn = r[b], mid;
    for(; ln <= rn;) {
        mid = (ln + rn) >> 1;
        if(an[mid] < v) ln = mid + 1;
        else rn = mid - 1;
    }
    return ln - l[b]; 
}

inline ll cnt(int x, int y, ll v) {
    ll res = 0;
    if(pos[x] == pos[y]) {
        for(int i = x; i <= y; i++)
            if(a[i] < v)
                res++;
    } else {
        for(int i = x; i <= r[pos[x]]; i++) 
            if(a[i] < v)
                res++;

        for(int i = l[pos[y]]; i <= y; i++) 
            if(a[i] < v)
                res++;

        for(int i = pos[x] + 1; i <= pos[y] - 1; i++) 
            res += getNum(i, v);
    }
    return res;
}

inline ll query(int x, int y, ll c) {
    ll ln = 0, rn = Maxn, mid, res = 0;
    for(; ln <= rn;) {
        mid = (ln + rn) >> 1;
        if(cnt(x, y, mid) < c) ln = mid + 1;
        else {
            rn = mid - 1;
            res = mid;
        }
    }
    return res - 1;
}

int main() {
    read(n), read(m);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
        an[i] = a[i];
    }

    bnum = sqrt(n);
    for(int i = 1; i <= bnum; i++) {
        l[i] = (i - 1) * bnum + 1;
        r[i] = i * bnum;
    }
    if(r[bnum] < n) {
        r[++bnum] = n;
        l[bnum] = r[bnum - 1] + 1;
    }
    for(int i = 1; i <= bnum; i++) {
        for(int j = l[i]; j <= r[i]; j++)
            pos[j] = i;
        sort(an + l[i], an + r[i] + 1);
    }   

    for(char op[5]; m--;) {
        scanf("%s", op);
        if(op[0] == 'C') {
            int x, v;
            read(x), read(v);
            modify(x, v);
        } else {
            int x, y, c;
            read(x), read(y), read(c);
            printf("%lld\n", query(x, y, c));
        }
    }
    return 0;
}