树套树板子
本来打算写大佬口胡的树状数组套主席树的
然而我根本写不来
网上随便抄了一篇线段树套Treap的
跑的飞慢
1 // luogu-judger-enable-o2 2 //minamoto 3 #include<bits/stdc++.h> 4 #define inf 2147483647 5 using namespace std; 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<21],*p1=buf,*p2=buf; 8 inline int read(){ 9 #define num ch-'0' 10 char ch;bool flag=0;int res; 11 while(!isdigit(ch=getc())) 12 (ch=='-')&&(flag=true); 13 for(res=num;isdigit(ch=getc());res=res*10+num); 14 (flag)&&(res=-res); 15 #undef num 16 return res; 17 } 18 char sr[1<<21],z[20];int C=-1,Z; 19 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} 20 inline void print(int x){ 21 if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; 22 while(z[++Z]=x%10+48,x/=10); 23 while(sr[++C]=z[Z],--Z);sr[++C]=' '; 24 } 25 const int N=50005; 26 int val[N],n,m,a,b,c; 27 struct node{ 28 node* ch[2]; 29 int rank,val,size; 30 node (int x){val=x,rank=rand(),size=1,ch[0]=ch[1]=NULL;} 31 void up(){ 32 size=1; 33 if(ch[0]) size+=ch[0]->size; 34 if(ch[1]) size+=ch[1]->size; 35 } 36 }; 37 inline int s(node* p){return p?p->size:0;} 38 node* rt[N*4]; 39 void rotate(node* &p,int d){ 40 node* k=p->ch[d^1];p->ch[d^1]=k->ch[d],k->ch[d]=p; 41 p->up(),k->up(),p=k; 42 } 43 void insert(node* &p,int val){ 44 if(p==NULL) return (void)(p=new node(val)); 45 if(val<p->val){ 46 insert(p->ch[0],val); 47 if(p->ch[0]->rank>p->rank) rotate(p,1); 48 } 49 else{ 50 insert(p->ch[1],val); 51 if(p->ch[1]->rank>p->rank) rotate(p,0); 52 } 53 p->up(); 54 } 55 void build(int l,int r,int p){ 56 for(int i=l;i<=r;++i) insert(rt[p],val[i]); 57 if(l==r) return; 58 int mid=(l+r)>>1; 59 build(l,mid,p<<1); 60 build(mid+1,r,p<<1|1); 61 } 62 void remove(node* &p,int val){ 63 if(p==NULL) return; 64 if(val==p->val){ 65 if(p->ch[0]&&p->ch[1]){ 66 int d=(p->ch[0]->rank > p->ch[1]->rank); 67 rotate(p,d),remove(p->ch[d],val); 68 } 69 else{ 70 node* u=(p->ch[0]==NULL)?p->ch[1]:p->ch[0]; 71 delete p; 72 p=u; 73 } 74 } 75 else if(val<p->val) remove(p->ch[0],val); 76 else remove(p->ch[1],val); 77 if(p) p->up(); 78 } 79 inline int find_rank(node* p,int val){ 80 int sum=0; 81 while(p){ 82 (val>p->val)?(sum+=s(p->ch[0])+1,p=p->ch[1]):(p=p->ch[0]); 83 } 84 return sum; 85 } 86 int tree_rank(int l,int r,int p,int val){ 87 if(a<=l&&b>=r) return find_rank(rt[p],val); 88 int mid=(l+r)>>1,res=0; 89 if(a<=mid) res+=tree_rank(l,mid,p<<1,val); 90 if(b>mid) res+=tree_rank(mid+1,r,p<<1|1,val); 91 return res; 92 } 93 inline int divide_rank(int val){ 94 int l=0,r=1e8; 95 while(l<=r){ 96 int mid=(l+r)>>1; 97 int check=tree_rank(1,n,1,mid)+1; 98 if(check<=val) l=mid+1; 99 else r=mid-1; 100 } 101 return r; 102 } 103 inline int Pre(int l,int r,int val){ 104 int tmp=tree_rank(1,n,1,val); 105 int res=divide_rank(tmp); 106 return res==-1?-inf:res; 107 } 108 inline int re(int l,int r,int val){ 109 int tmp=tree_rank(1,n,1,val+1)+1; 110 int res=divide_rank(tmp); 111 return res==1e8?inf:res; 112 } 113 void change(int l,int r,int p,int pos,int Pre,int now){ 114 remove(rt[p],Pre); 115 insert(rt[p],now); 116 if(l==r) return; 117 int mid=(l+r)>>1; 118 if(pos<=mid) change(l,mid,p<<1,pos,Pre,now); 119 else change(mid+1,r,p<<1|1,pos,Pre,now); 120 } 121 int main(){ 122 //freopen("testdata.in","r",stdin); 123 //freopen("check.out","w",stdout); 124 n=read(),m=read(); 125 for(int i=1;i<=n;++i) val[i]=read(); 126 build(1,n,1); 127 while(m--){ 128 int opt=read(); 129 switch(opt){ 130 case 1:{ 131 a=read(),b=read(),c=read(); 132 print(tree_rank(1,n,1,c)+1); 133 break; 134 } 135 case 2:{ 136 a=read(),b=read(),c=read(); 137 print(divide_rank(c)); 138 break; 139 } 140 case 3:{ 141 a=read(),b=read(); 142 change(1,n,1,a,val[a],b),val[a]=b; 143 break; 144 } 145 case 4:{ 146 a=read(),b=read(),c=read(); 147 print(Pre(a,b,c)); 148 break; 149 } 150 case 5:{ 151 a=read(),b=read(),c=read(); 152 print(re(a,b,c)); 153 break; 154 } 155 } 156 } 157 Ot(); 158 return 0; 159 }