Dynamic Rankings 整体二分

Dynamic Rankings
动态区间第K大，方法有很多可以用或者是带修改主席树，这个题目相较于不带修改的区间第K大，整体二分的优势就体现出来了。又快又好打

#include <bits/stdc++.h>

const int MAXN = 500000;

using namespace std;

int n,m,top,cnt,cnt1;
int H[MAXN],last[MAXN],ans[MAXN],C[MAXN];

struct node{
    int l,r,k,id;
}Q[MAXN],Tl[MAXN],Tr[MAXN];

inline void init()
{
    int x;
    for(int i = 1;i <= n;i++){
        scanf("%d",&x);
        last[i] = x;
        Q[++cnt].l = i;
        Q[cnt].r = x;
        Q[cnt].id = 0;
        H[++top] = x;
    }
    char s[10];
    int l,r;
    for(int i = 1;i <= m;i++){
        scanf("%s",s);
        if(s[0] == 'Q'){
            cnt++;
            scanf("%d %d %d",&Q[cnt].l,&Q[cnt].r,&Q[cnt].k);
            Q[cnt].id = ++cnt1;
        }
        else {
            cnt++;
            scanf("%d %d",&l,&r);
            Q[cnt].l = l;
            Q[cnt].r = last[l];
            last[l] = r;
            Q[cnt].id = -1;
            Q[++cnt].l = l;
            Q[cnt].r = r;
            Q[cnt].id = 0;
            H[++top] = r;
        }
    }
    sort(H+1,H+top+1);
    top = unique(H+1,H+1+top) - H;
    top--;
    
    for(int i = 1;i <= cnt;i++){
        if(Q[i].id <= 0){
            Q[i].r = lower_bound(H+1,H+1+top,Q[i].r) - H;
        }
    }

}

inline int lowbit(int x){return x & -x;}

inline void add(int x,int d){
    for(;x <= n;x += lowbit(x)) C[x] += d;
}

inline int sum(int x){
    int ret = 0;
    for(;x;x -= lowbit(x)) ret += C[x];
    return ret;
}

void solve(int L,int R,int st,int ed){
    if(st > ed) return;
    if(L == R){
        for(int i = st;i <= ed;i++)
            if(Q[i].id > 0)
                ans[Q[i].id] = H[L];
        return;
    }
    int M = (L + R) >> 1;
    int lc = 0,rc = 0;
    for(int i = st;i <= ed;i++){
        if(Q[i].id == -1){
            if(Q[i].r <= M) add(Q[i].l,-1),Tl[++lc] = Q[i];
            else Tr[++rc] = Q[i];
        }
        else if(Q[i].id == 0){
            if(Q[i].r <= M) add(Q[i].l,1),Tl[++lc] = Q[i];
            else Tr[++rc] = Q[i];
        }
        else {
            int x = sum(Q[i].r) - sum(Q[i].l - 1);
            if(Q[i].k <= x) Tl[++lc] = Q[i];
            else Q[i].k -= x,Tr[++rc] = Q[i];
        }
    }
    for(int i = ed;i >= st;i--) {
        if(Q[i].id == -1 && Q[i].r <= M) add(Q[i].l,+1);
        if(Q[i].id == 0 && Q[i].r <= M) add(Q[i].l,-1);
    }
    
    for(int i = 1;i <= lc;i++) Q[st+i-1] = Tl[i];
    for(int i = 1;i <= rc;i++) Q[st+lc+i-1] = Tr[i];
    
    solve(L,M,st,st+lc-1);solve(M+1,R,st+lc,ed);
}

int main()
{

    scanf("%d %d",&n,&m);
    init();
    solve(1,top,1,cnt);
    for(int i = 1;i <= cnt1;i++)
        printf("%d\n",ans[i]);
    return 0;
}