Description
Solution
直接splay搞定吧。。似乎非旋treap也ok？
我已经菜到模板题都写不出来了qaq
Code
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int n,m,A[20010]; struct Splay { int rt,cnt=0; int ch[120010][2],num[120010][2],sz[120010],fa[120010]; void pushup(int k){ sz[k]=sz[ch[k][0]]+sz[ch[k][1]]+num[k][1]-num[k][0]+1;} void build(int &k,int l,int r) { k=++cnt; int mid=(l+r)/2; num[k][0]=num[k][1]=A[mid]; if (l<mid) build(ch[k][0],l,mid-1); if (mid<r) build(ch[k][1],mid+1,r); fa[ch[k][0]]=fa[ch[k][1]]=k; pushup(k); } void rotate(int x,int &rt) { int y=fa[x],k=ch[y][1]==x; ch[y][k]=ch[x][k^1];fa[ch[y][k]]=y; if (y==rt) rt=x;else ch[fa[y]][ch[fa[y]][1]==y]=x; fa[x]=fa[y]; fa[y]=x;ch[x][k^1]=y; pushup(y);pushup(x); } void splay(int x,int &rt) { int y; while (x!=rt) { y=fa[x]; if (y!=rt&&(ch[fa[y]][1]==y)==(ch[y][1]==x)) rotate(y,rt); rotate(x,rt); } } int work(int x,int k) { if (sz[ch[x][0]]>=k) return work(ch[x][0],k); if (sz[x]-sz[ch[x][1]]<k) return work(ch[x][1],k-sz[x]+sz[ch[x][1]]); k-=sz[ch[x][0]];int son; if (k!=1) { son=++cnt; num[son][0]=num[x][0];num[son][1]=num[son][0]+k-2; num[x][0]=num[son][1]+1; fa[son]=x; ch[son][0]=ch[x][0]; ch[x][0]=son; pushup(son); k=1; } if (k!=num[x][1]-num[x][0]+1) { son=++cnt; num[son][0]=num[x][0]+k; num[son][1]=num[x][1]; num[x][1]=num[son][0]-1; fa[son]=x; ch[son][1]=ch[x][1]; ch[x][1]=son; pushup(son); } return x; } void insert(int p,int a,int b) { int x1=work(rt,p),x2=work(rt,p+1); splay(x1,rt); splay(x2,ch[x1][1]); int son=++cnt; num[son][0]=a;num[son][1]=b;fa[son]=x2; ch[x2][0]=son; sz[son]=b-a+1; pushup(x2); pushup(x1); } void remove(int a,int b) { int x1=work(rt,a-1),x2=work(rt,b+1); splay(x1,rt); splay(x2,ch[x1][1]); ch[x2][0]=0; pushup(x2); pushup(x1); } int query(int x,int q) { if (!x) return 0; if (sz[ch[x][0]]>=q) return query(ch[x][0],q); if (sz[x]-sz[ch[x][1]]>=q) {q-=sz[ch[x][0]];return num[x][0]+q-1;} return query(ch[x][1],q-sz[x]+sz[ch[x][1]]); } }splay; int _type,p,a,b; int main() { scanf("%d%d",&n,&m); n++; for (int i=2;i<=n;i++) scanf("%d",&A[i]); n++; splay.build(splay.rt,1,n); for (int i=1;i<=m;i++) { scanf("%d",&_type); if (!_type) { scanf("%d%d%d",&p,&a,&b);p++; splay.insert(p,a,b); } if (_type==1) { scanf("%d%d",&a,&b);a++;b++; splay.remove(a,b); } if (_type==2) { scanf("%d",&p);p++; printf("%d ",splay.query(splay.rt,p)); } } }