fork download
copy 
  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. #define mid (l+r>>1)
  5. int n,m,rs,b[60000],q[10000][3];
  6. char str[1000000],*p=str;
  7. namespace CT{
  8. 	struct Node{Node*c[2];int s;}st[2500000],*stp,*T[50001];int S;
  9. 	Node*Build(int l=0,int r=S){Node*N=stp++;if(l+1!=r)N->c[0]=Build(l,mid),N->c[1]=Build(mid,r);return N;}
  10. 	inline Node*Insert(Node*y,int i,int j){
  11. 		Node*R=stp++,*x=R;int l=0,r=S;
  12. 		for(x->s=y->s+j;l+1!=r;x->s=y->s+j)if(i<mid)x->c[0]=stp++,x->c[1]=y->c[1],x=x->c[0],y=y->c[0],r=mid;
  13. 		else x->c[0]=y->c[0],x->c[1]=stp++,x=x->c[1],y=y->c[1],l=mid;
  14. 		return R;
  15. 	}struct ChairTree{
  16. 		Node*T[16];int s;
  17. 		inline ChairTree(){s=0;}
  18. 		inline ChairTree(Node*x){s=1;T[0]=x;}
  19. 		inline void operator+=(Node*x){T[s++]=x;}
  20. 		inline operator int()const{int i=s,ans=0;while(i--)ans+=T[i]->c[0]->s;return ans;}
  21. 		inline bool operator^=(bool c){int i=s;while(i--)T[i]=T[i]->c[c];return c;}
  22. 	};
  23. }namespace BIT{
  24. 	CT::Node*A[50001];
  25. 	inline void Init(){int i=n;A[i]=CT::Build();while(--i)A[i]=A[n];}
  26. 	inline void I(int x,int i,int y){for(;x<=n;x+=x&-x)A[x]=CT::Insert(A[x],i,y);}
  27. 	inline void Q(CT::ChairTree&R,int x){for(;x;x-=x&-x)R+=A[x];}
  28. }inline int getint(){
  29. 	int re=0;
  30. 	while(*p<'0'||*p>'9')p++;
  31. 	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
  32. 	return re;
  33. }struct Q{int v,i;bool operator<(const Q&a)const{return v<a.v;}}rk[60000];
  34. int main(){
  35. 	int i,j,l,r;bool C;fread(p,1,1000000,stdin);
  36. 	n=getint();m=getint();rs=0;CT::stp=CT::st;CT::S=1;
  37. 	for(i=-1;++i!=n;rs++)rk[rk[rs].i=rs].v=getint();
  38. 	for(i=m;i--;){
  39. 		while(*p!='Q'&&*p!='C')p++;
  40. 		if(*p=='Q')q[i][0]=getint(),q[i][1]=getint(),q[i][2]=getint();
  41. 		else q[i][0]=getint(),rk[rk[rs].i=rs].v=getint(),q[i][2]=0,rs++;
  42. 	}sort(rk,rk+rs);b[rk[0].i]=0;
  43. 	for(i=0;++i!=rs;b[rk[i].i]=CT::S-1)if(rk[i].v!=rk[i-1].v)rk[CT::S++].v=rk[i].v;
  44. 	BIT::Init();
  45. 	for(CT::T[rs=i=0]=BIT::A[n];i++!=n;)CT::T[i]=Insert(CT::T[i-1],b[rs++],1);
  46. 	while(m--)if(q[m][2]){
  47. 		CT::ChairTree a,b,c=CT::T[q[m][1]],d=CT::T[q[m][0]-1];
  48. 		BIT::Q(a,q[m][1]);
  49. 		BIT::Q(b,q[m][0]-1);
  50. 		for(l=0,r=CT::S;l+1!=r;a^=b^=c^=d^=C)if((i=a+c-b-d)>=q[m][2])C=0,r=mid;
  51. 		else C=1,l=mid,q[m][2]-=i;
  52. 		printf("%d\n",rk[l].v);
  53. 	}else{
  54. 		BIT::I(q[m][0],b[q[m][0]-1],-1);
  55. 		BIT::I(q[m][0],b[q[m][0]-1]=b[rs++],1);
  56. 	}return 0;
  57. }
  58.  
Runtime error #stdin #stdout 0.06s 34216KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2Jp5W
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!