Luogu Dynamic Ranking (带修改的主席树)

题目大意：

网址：https://www.luogu.org/problemnew/show/2617
给定一个序列a[1]、a[2]、...、a[N]，完成M个操作，操作有两种：
[1]Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。
[2]C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t。
数据范围： \(1≤n≤10000，1≤m≤10000\)

解法：带修改的主席树：

原本的主席树是维护了一个线段树前缀。
那么前缀有没有想到什么东西？树状数组\(Bits\)是不是很 ...... ?
那么现在，我们用树状数组套主席树，不就可以实现带修改的可持久化了吗。
具体来说 \(T[1]维护rt[1]\) , \(T[2]维护rt[1]、rt[2]\) , \(T[3]维护rt[3]\) ......
就与树状数组是一样的。
那么现在，两个具体的操作：

修改：

修改需要修改\(logN\)棵主席树，将涉及修改节点的\(log\)个主席树先删后加点即可。
具体来说，修改x位置的，则要修改：for(x; x; x -= (x&-x))Update(rt[x]);

查询：

考虑一下树状数组的查询，是用到了两个前缀相减的方法。
那么这里也是一样的，查询\([L,R]\)就是\([1,R]\)的值减去\([1,(L-1)]\)的值。
具体来说，对于\([L,R]\)区间对应的主席树，每个点的sum值为：
\[Sum[ro] = ∑sum[ro[u]] - ∑sum[ro[v]];u∈[1,R],v∈[1,L-1]\]
那么以查询第区间第\(k\)大为例子，直接将\(k\)与节点的\(Sum\)值比较即可。

总复杂度：

时间复杂度：\(O(NLog^2N)\) ，空间复杂度\(O(NLog^2N)\)

两个去重、二分的函数：

Unique去重函数：

对于a[1]、a[2]、....、a[N]，去重函数为：
\[Length = Unique(a+1,a+N+1) - a - 1;\]
Unique函数返回的是去重后后面第一个空位置，所以要长度减1。
去重完的序列即为a[1]、a[2]、....、a[Length];

Lower_Bound二分函数：

对于序列a[1]、a[2]、....、a[N]，查找<=x的最接近数的序列位置，为：
k = lower_bound(a+1,a+N+1,x) - oder;
low_bound返回的是那个值的地址，应该要与第0个位置相减得到其确切的位置。

具体实现代码：

#include<bits/stdc++.h>
#define RG register
#define IL inline
#define maxn 200005
using namespace std;

int N,M,Q,cntl,cntr,lg;
struct Ques{int l,r,k;}qs[maxn];
int rt[2*maxn],ls[20*maxn],rs[20*maxn],sum[20*maxn],tpl[maxn],tpr[maxn];
int a[maxn],oder[2*maxn],cnt;

void Update(int &ro,int l,int r,int ps,int chg){
    if(!ro)ro = ++cnt;
    sum[ro] += chg;
    if(l == r)return;
    RG int mid = (l+r)>>1;
    if(ps <= mid)Update(ls[ro],l,mid,ps,chg);
    else Update(rs[ro],mid+1,r,ps,chg);
}

IL void Modify(RG int ps,RG int chg){
    RG int k = lower_bound(oder+1,oder+lg+1,a[ps]) - oder;
    for(RG int i = ps; i <= N; i += (i&-i))
        Update(rt[i],1,lg,k,chg);
}

int Query(int l,int r,int k){
    if(l == r)return l;
    RG int mid = (l+r)>>1,Sum = 0;
    for(RG int i = 1; i <= cntl; i ++)Sum -= sum[ls[tpl[i]]];
    for(RG int i = 1; i <= cntr; i ++)Sum += sum[ls[tpr[i]]];
    if(k <= Sum){
        for(RG int i = 1; i <= cntl; i ++)tpl[i] = ls[tpl[i]];
        for(RG int i = 1; i <= cntr; i ++)tpr[i] = ls[tpr[i]];
        return Query(l,mid,k);
    }
    else{
        for(RG int i = 1; i <= cntl; i ++)tpl[i] = rs[tpl[i]];
        for(RG int i = 1; i <= cntr; i ++)tpr[i] = rs[tpr[i]];
        return Query(mid+1,r,k-Sum);
    }
}

IL int Get(RG int l,RG int r,RG int k){
    cntl = cntr = 0;
    for(RG int i = (l-1); i ; i -= (i&-i))
        tpl[++cntl] = rt[i];
    for(RG int i = r; i ; i -= (i&-i))
        tpr[++cntr] = rt[i];
    return Query(1,lg,k);
}

int main(){
    freopen("testdate.in","r",stdin);
    cin>>N>>M;
    for(RG int i = 1; i <= N; i ++)
        cin>>a[i]  , oder[++lg] = a[i];
    char od; int l,r,k;
    for(RG int i = 1,c; i <= M; i ++){
        cin>>od;
        if(od == 'Q')cin>>l>>r>>k,qs[i] = (Ques){l,r,k};
        else cin>>l>>k,qs[i] = (Ques){l,0,k},oder[++lg] = k;
    }
    sort(oder+1,oder+lg+1);
    lg = unique(oder+1,oder+lg+1) - oder - 1;
    for(RG int i = 1; i <= N; i ++)Modify(i,1);
    for(RG int i = 1; i <= M; i ++)
    {
        if(!qs[i].r){
            Modify(qs[i].l , -1);
            a[qs[i].l] = qs[i].k;
            Modify(qs[i].l , 1);
        }
        else printf("%d\n",oder[Get(qs[i].l,qs[i].r,qs[i].k)]);
    }
    return 0;
}

秒客网