BZOJ1901 Dynamic Rankings

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

struct point{
	int fa,lson,rson;
	int data,muti,size;
}node[400010];

char od,te;
const int maxn=40010;
int top=0,minnum=9999999,maxnum=-9999999,n,vv,cnt;
int tree[maxn],l[maxn],r[maxn],a[maxn],lt[maxn],rt[maxn];

int newsplay(int key){
	top++;
	node[top].size=node[top].muti=1;
	node[top].lson=node[top].rson=node[top].fa=0;
	node[top].data=key;
	return top;
}

void zig(int now){
	int tf=node[now].fa,te=node[now].size-node[node[now].lson].size;
	if	((node[node[tf].fa].lson)==tf)	
		node[node[tf].fa].lson=now;
	else	node[node[tf].fa].rson=now;
	node[tf].rson=node[now].lson;
	node[now].lson=tf;
	node[now].fa=node[tf].fa;node[tf].fa=now;
	if  (node[tf].rson)  node[node[tf].rson].fa=tf;
	node[now].size=node[tf].size;
	node[tf].size-=te;
}

void zag(int now){
	int tf=node[now].fa,te=node[now].size-node[node[now].rson].size;
	if	((node[node[tf].fa].lson)==tf)	
		node[node[tf].fa].lson=now;
	else	node[node[tf].fa].rson=now;
	node[tf].lson=node[now].rson;
	node[now].rson=tf;
	node[now].fa=node[tf].fa;node[tf].fa=now;
	if  (node[tf].lson) node[node[tf].lson].fa=tf;
	node[now].size=node[tf].size;
	node[tf].size-=te;
}

void splay(int root,int now){
	if  (root==now || node[now].fa==root) return  ;
	while   (root!=node[now].fa){
		if  (node[node[now].fa].fa==root){
	    	if  (node[node[now].fa].lson==now)   zag(now);else   zig(now);
	    	return  ;
		}
		if  (node[node[node[now].fa].fa].lson==node[now].fa)
		    if  (node[node[now].fa].lson==now){zag(now);zag(now);}
		    else	{zig(now);zag(now);}
		else
			if  (node[node[now].fa].lson==now){zag(now);zig(now);}
	    	else	{zig(now);zig(now);}
	}
}

void insert(int now,int key){
	int x=now;
	while   (1){
		node[x].size++;
		if  (node[x].data==key){
			node[x].muti++;
			splay(now,x);
			return  ;
		}
		if  (node[x].data>key){
			if  (!node[x].lson){
				node[x].lson=newsplay(key);
				node[node[x].lson].fa=x;
				splay(now,node[x].lson);
				return  ;
			}else   x=node[x].lson;
		}
		else
		    if  (!node[x].rson){
				node[x].rson=newsplay(key);
				node[node[x].rson].fa=x;
				splay(now,node[x].rson);
				return  ;
		    }else   x=node[x].rson;
	}
}

void deldata(int now,int key){
	int x=now;
    while   (1){
		node[x].size--;
		if  (node[x].data==key){
			node[x].muti--;
			return  ;
		}
		if  (node[x].data>key)  x=node[x].lson;
		else x=node[x].rson;
	}
}

int count(int now,int key){
	int res=0,x=now;
	while   (x){
		if  (node[x].data==key){
			res+=node[x].size-node[node[x].rson].size;
			splay(now,x);
			return res;
		}
		if  (node[x].data>key)  x=node[x].lson;
		else{
			res+=node[x].size-node[node[x].rson].size;
			x=node[x].rson;
		}
	}
	return res;
}

void build(int now,int lm,int rm){
	tree[now]=newsplay(a[lm]);
	l[now]=lm;r[now]=rm;
	if  (lm==rm){
		lt[now]=rt[now]=0;
		return  ;
	}
	for (int i=lm+1;i<=rm;i++){
		insert(tree[now],a[i]);
	}
	build(now*2,lm,(lm+rm)/2);
	build(now*2+1,(lm+rm)/2+1,rm);
	lt[now]=now*2;rt[now]=now*2+1;
}

void query(int now,int lm,int rm,int key){
	if  (l[now]>rm || r[now]<lm)    return  ;
	if  (l[now]>=lm && r[now]<=rm){
		cnt+=count(tree[now],key);
		return  ;
	}
	if  (lt[now])   query(lt[now],lm,rm,key);
	if  (rt[now])   query(rt[now],lm,rm,key);
	return  ;
}

void change(int now,int tar,int ori,int key){
	if  (l[now]>tar || r[now]<tar)  return  ;
	deldata(tree[now],ori);
	insert(tree[now],key);
	if  (l[now]!=r[now]){
		change(lt[now],tar,ori,key);
		change(rt[now],tar,ori,key);
	}
	return  ;
}

void scan(int &x){
	te=getchar();
	while   (te<'0' || te>'9')  te=getchar();
	x=te-'0';te=getchar();
	while   (te>='0' && te<='9'){
		x=x*10+te-'0';
		te=getchar();
	}
}

int main(){
	scanf("%d%d",&n,&vv);
	for (int i=1;i<=n;i++){
		int cl;scan(cl);a[i]=cl;
		minnum=min(minnum,a[i]);
		maxnum=max(maxnum,a[i]);
	}
	scanf("
");
	build(1,1,n);
	while   (vv--){
		int cl,cr,th;
		od=getchar();
		if  (od=='Q'){
			scan(cl);scan(cr);scan(th);
			int ll=minnum,rr=maxnum;
			while   (ll<rr){
				cnt=0;
				query(1,cl,cr,(ll+rr)/2);
				if  (cnt>=th)   rr=(ll+rr)/2;
				else    ll=(ll+rr)/2+1;
			}
			printf("%d
",ll);
		}
		else{
			scan(cl);scan(cr);
			minnum=min(minnum,cr);
			maxnum=max(maxnum,cr);
			change(1,cl,a[cl],cr);
			a[cl]=cr;
		}
	}
	return 0;
}