题解 P2617 【Dynamic Ranking】
看了看下面的题解，似乎没有用线段树套平衡树做的，来发题解，
首先，我们可以用线段树维护每一个区间，对于每一个区间，我们都可以维护一棵平衡树，表示该区间内的所有的树，所以对于每个数，都会在平衡树中出现logn次，因此空间复杂度就是（nlogn），
对于修改操作（x，t），我们只需要在x出现的logn个区间中去修改，而每个区间就是一颗平衡树，因此修改一次是（logn）的二次方；
对于查询操作，我们可以去二分【l，r】中第k大的值的大小，然后检验【l，r】中小于二分值的数的个数；二分logn，检验log2n，所以总的时间复杂度就是n*log3n
以下是代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#define maxn 1000000+10
#define inf 0x7f7f7f7f
using namespace std;
int ch[maxn][2],val[maxn],siz[maxn],fa[maxn],a[maxn];
int root[maxn],ls[maxn],rs[maxn],cnt[maxn];
int n,m,sz,ct,ROOT;
void up(int x){
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];
}
void rotate(int x){
int y=fa[x],z=fa[y],k=x==ch[y][1];
ch[z][y==ch[z][1]]=x; fa[x]=z;
ch[y][k]=ch[x][k^1]; fa[ch[x][k^1]]=y;
ch[x][k^1]=y; fa[y]=x;
up(y);up(x);
}
void splay(int &rt,int x,int goal){
while(fa[x]!=goal){
int y=fa[x],z=fa[y];
if(z!=goal)
(x==ch[y][0])^(y==ch[z][1])?rotate(x):rotate(y);
rotate(x);
}if(goal==0)rt=x;
}
void find(int &rt,int x){
int now=rt;
while(ch[now][x>val[now]] && x!=val[now])now=ch[now][x>val[now]];
splay(rt,now,0);
}
int nex(int &rt,int x,int f){
find(rt,x);int now=rt;
if((x<val[now] && f==1) || (x>val[now] && f==1))return now;
now=ch[now][f];
while(ch[now][f^1])now=ch[now][f^1];
return now;
}
void del(int &rt,int x){
int nex0=nex(rt,x,0),nex1=nex(rt,x,1);
splay(rt,nex0,0);splay(rt,nex1,nex0);
if(cnt[ch[nex1][0]]==1){
ch[nex1][0]=0;splay(rt,nex1,0);
}else cnt[ch[nex1][0]]--,splay(rt,ch[nex1][0],0);
}
void ins(int &rt,int x){
int now=rt,ff=0;
while(now && x!=val[now])ff=now,now=ch[now][x>val[now]];
if(!now){
now=++sz;if(ff)ch[ff][x>val[ff]]=now;
ch[now][0]=ch[now][1]=0;siz[now]=cnt[now]=1;
fa[now]=ff;val[now]=x;
}else cnt[now]++;splay(rt,now,0);
}
void inint(int &now,int l,int r,int x,int v){
if(!now)now=++ct;
ins(root[now],v);
if(l==r)return;
int mid=l+r>>1;
if(x<=mid)inint(ls[now],l,mid,x,v);
else inint(rs[now],mid+1,r,x,v);
}
void change(int now,int l,int r,int x,int v){
del(root[now],a[x]);ins(root[now],v);
if(l==r)return;int mid=l+r>>1;
if(x<=mid)change(ls[now],l,mid,x,v);
else change(rs[now],mid+1,r,x,v);
}
int get(int now,int l,int r,int L,int R,int x){
if(R<l || r<L)return 0;
if(L<=l&&r<=R){
find(root[now],x);int rt=root[now];
if(val[rt]>=x)return siz[ch[rt][0]]-1;
if(val[rt]<x )return siz[ch[rt][0]]+cnt[rt]-1;
}int mid=l+r>>1;
return get(ls[now],l,mid,L,R,x)+get(rs[now],mid+1,r,L,R,x);
}
int erfen(int l,int r,int rk){
int ll=0,rr=inf;
while(ll<=rr){
int mid=ll+rr>>1;
if(get(ROOT,1,n,l,r,mid)<rk)ll=mid+1;
else rr=mid-1;
}return ll-1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
inint(ROOT,1,n,i,a[i]);
}
for(int i=1;i<=ct;i++){
ins(root[i],inf);ins(root[i],-inf);
}
for(int i=1;i<=m;i++){
char opt;int l,r,k,x,t;
cin>>opt;
if(opt=='Q'){
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",erfen(l,r,k));
}else {
scanf("%d%d",&x,&t);
change(ROOT,1,n,x,t);a[x]=t;
}
}
}