题目大意：
网址：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 200005using 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;}
