Dynamic Rankings（树状数组套权值线段树）

这道题就是一个带修区间第k大的问题，可以用cdq分治做，也可以用树套树做。由于有修改，如果暴力在主席树上修改，时间复杂度就爆炸了，单个修改都是\(O(nlogn)\)的。再看看查询，是\(O(logn)\)的，这就启发我们可不可以把它们两个平均一下，于是就用到了树状数组。在树状数组的每个区间上都建一颗权值线段树，维护此区间上每个值出现的个数（链+权值线段树=主席树，树状数组+权值线段树=带修主席树【滑稽】）。那么修改某一个数的值，会牵动到树状数组上logn个区间，然后权值线段树单点修改时间为\(O(logn)\)，总时间是\(O(log^2nn)\)的。查询区间\([l, r]\)的第k大值，需要得到\([1, l-1]\)和\([1, r]\)的权值线段树，然后将它们相减，依然会牵动到logn个区间，由于权值线段树区间查询时间是\(O(logn)\)，总时间也是\(O(logn^2n)\)的。注意要离散化，这题还是挺难写的。

所以说，数据结构可以平衡操作的时间复杂度。

P.S. 三个月后的我看到这篇博客仿佛看到了救星（要讲课啊妈蛋）

P.A. 四个月后的我忽然发现这个东西的本质和主席树的本质是不同的，因为主席树的每棵权值线段树是继承与前一棵权值线段树的，而它只是把插入和查询的前提复杂度变成了\(O(logn)\)而已。不过，我还是倾向于叫它带修主席树，因为它是主席树应用到树状数组上的自然推论。

#include <cctype>

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=2e4+5;

int n, m, a[maxn], b[maxn], cntb, rt[maxn];

int c1[maxn], c2[maxn], c3[maxn];

int size[maxn*400], cseg, ls[maxn*400], rs[maxn*400];

int tset1[maxn], tset2[maxn], cnt1, cnt2;

inline int lowbit(int x){ return x&(-x); } //树状数组上的权值线段树

void ins(int &now, int l, int r, int pos, int v){

    if (!now) now=++cseg; size[now]+=v;

    if (l==r) return; int mid=(l+r)>>1;

    if (pos<=mid) ins(ls[now], l, mid, pos, v);

    else ins(rs[now], mid+1, r, pos, v);

}

void add(int x, int v){

    int k=lower_bound(b+1, b+cntb+1, a[x])-b;

    for (int i=x; i<=n; i+=lowbit(i))

        ins(rt[i], 1, cntb, k, v);

}

int query(int l, int r, int v){  //logn个权值线段树一起跳

    if (l==r) return l;

    int sum=0, mid=(l+r)>>1;

    for (int i=1; i<=cnt1; ++i) sum-=size[ls[tset1[i]]];

    for (int i=1; i<=cnt2; ++i) sum+=size[ls[tset2[i]]];

    if (v<=sum){

        for (int i=1; i<=cnt1; ++i) tset1[i]=ls[tset1[i]];

        for (int i=1; i<=cnt2; ++i) tset2[i]=ls[tset2[i]];

        return query(l, mid, v);

    } else {

        for (int i=1; i<=cnt1; ++i) tset1[i]=rs[tset1[i]];

        for (int i=1; i<=cnt2; ++i) tset2[i]=rs[tset2[i]];

        return query(mid+1, r, v-sum);

    }

}

inline void get(int &x){

    char c; int flag=1;

    for (; !isdigit(c=getchar()); ) if (c=='-') flag=-1;

    for (x=c-48; c=getchar(), isdigit(c); )

        x=(x<<3)+(x<<1)+c-48;

    if (flag==-1) x=-x;

}

int main(){

    get(n); get(m); char c;

    for (int i=1; i<=n; ++i) get(a[i]), b[++cntb]=a[i];

    for (int i=0; i<m; ++i){

        while (!isgraph(c=getchar()));

        get(c1[i]); get(c2[i]);

        if (c=='Q') get(c3[i]); else b[++cntb]=c2[i];

    }

    sort(b+1, b+cntb+1); cntb=unique(b+1, b+cntb+1)-b-1;

    for (int i=1; i<=n; ++i) add(i, 1);

    for (int i=0; i<m; ++i) if (c3[i]){

        cnt1=cnt2=0;  //把要查询的区间都标出来

        for (int j=c1[i]-1; j; j-=lowbit(j)) tset1[++cnt1]=rt[j];

        for (int j=c2[i]; j; j-=lowbit(j)) tset2[++cnt2]=rt[j];

        printf("%d\n", b[query(1, cntb, c3[i])]);

    } else { add(c1[i], -1); a[c1[i]]=c2[i]; add(c1[i], 1); }

    return 0;

}