pbds/rope的应用
题单介绍
也有非平衡树
```
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>t;
int m,a[100005],last,x,op;
int main(){
cin>>m;
for(int i=0;i<m;++i){
scanf("%d%d",&op,&x);
if(op==1)t.insert(x);
else if(op==2)t.erase(t.upper_bound(x));
else if(op==3)last=t.order_of_key(x)+1;
else if(op==4)last=*(t.find_by_order(x-1));
else if(op==5)last=*(--t.upper_bound(x));
else last=*(t.lower_bound(x));
if(op>=3)printf("%d\n",last);
}
return 0;
}
```
P4008文本编辑rope
```
#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
rope<char> p;
int n,gb,q,t;
string s,k;
char s1[1114514],l;
int main(){
cin>>n;
for(int i=0;i<n;i++){
t=0;
cin>>s;
if(s=="Move")cin>>gb;
else if(s=="Insert"){
cin>>q;
t=0;
while(t<q){
l=getchar();
if(32<=l&&l<=126)s1[t]=l,t++;
}
p.insert(gb,s1,q);
}else if(s=="Get"){
cin>>q;
cout<<p.substr(gb,q)<<"\n";
}else if(s=="Delete"){
cin>>q;
p.erase(gb,q);
}else if(s=="Prev")gb--;
else gb++;
}
return 0;
}
```
树套树
```cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>tp[2500005];
int n,m,a[50005],dx,ccf,dl,dr,k,pos;
struct op{
int l=-1,r=-1,vl,vr;
}t[2500005];
void js(int x){
int m=(t[x].vl+t[x].vr)/2;
t[dx].vl=t[x].vl,t[dx+1].vr=t[x].vr;
t[dx].vr=m,t[dx+1].vl=m+1;
t[x].l=dx,t[x].r=dx+1,dx+=2;
}
void xg(int x,int id,int v,int nbt){
if(t[x].vl!=t[x].vr&&t[x].l==-1)js(x);
if(nbt==0)tp[x].insert(id);
else tp[x].erase(tp[x].upper_bound(id));
if(t[x].l==t[x].r)return;
int m=(t[x].vl+t[x].vr)/2;
if(m>=v)xg(t[x].l,id,v,nbt);
else xg(t[x].r,id,v,nbt);
}
int q3(int x,int l,int r){
return tp[x].order_of_key(r+1)-tp[x].order_of_key(l);
}
int op1(int x,int vl,int vr,int l,int r){
if(vl>vr)return 0;
if(vl<=t[x].vl&&t[x].vr<=vr)return q3(x,l,r);
if(t[x].vl!=t[x].vr&&t[x].l==-1)js(x);
int m=(t[x].vl+t[x].vr)/2,ans=0;
if(vl<=m)ans+=op1(t[x].l,vl,vr,l,r);
if(vr>m)ans+=op1(t[x].r,vl,vr,l,r);
return ans;
}
int op2(int x,int l,int r,int k){
if(t[x].vl!=t[x].vr&&t[x].l==-1)js(x);
if(t[x].vl==t[x].vr)return t[x].vl;
if(q3(t[x].l,l,r)>=k)return op2(t[x].l,l,r,k);
return op2(t[x].r,l,r,k-q3(t[x].l,l,r));
}
int main(){
cin>>n>>m;
t[0].vl=0,t[0].vr=100000000,dx++;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
xg(0,i,a[i],0);
}
for(int i=0;i<m;i++){
scanf("%d",&ccf);
if(ccf==3)scanf("%d%d",&pos,&k);
else scanf("%d%d%d",&dl,&dr,&k);
if(ccf==1)printf("%d\n",op1(0,0,k-1,dl,dr)+1);
else if(ccf==2)printf("%d\n",op2(0,dl,dr,k));
else if(ccf==3)xg(0,pos,a[pos],1),a[pos]=k,xg(0,pos,k,0);
else if(ccf==4){
pos=op1(0,0,k-1,dl,dr);
if(pos==0)printf("-2147483647\n");
else printf("%d\n",op2(0,dl,dr,pos));
}else{
pos=op1(0,0,k,dl,dr);
if(pos==dr-dl+1)printf("2147483647\n");
else printf("%d\n",op2(0,dl,dr,pos+1));
}
}
return 0;
}
```