#include <cstdio> #include <iostream> using namespace std; const int nil=2*1e5;//nil表示不存在的节点 int son[200001][2],flag[200001],size[200001],v[200001]; int n,m; int root,cnt,fa[200001]; inline void swap(int &a,int &b){ int t=a; a=b;b=t; } inline void mark(int po){ swap(son[po][0],son[po][1]); flag[po]^=1; } inline void pushdown(int po){ int l=son[po][0],r=son[po][1]; if (flag[po]){ if (l!=nil) mark(l); if (r!=nil) mark(r); flag[po]^=1; } } inline int find(int num){ int po=root; while (1){ pushdown(po); if (size[son[po][0]]+v[po]==num) {return(po);continue;} if (size[son[po][0]]+v[po]>num) {po=son[po][0];continue;} if (size[son[po][0]]+v[po]<num) {num-=size[son[po][0]]+v[po],po=son[po][1];continue;} } } int build(int l,int r){ int mid=(l+r)>>1; size[mid]=min(r,n)-max(l,1)+1; son[mid][0]=son[mid][1]=nil; if (l<mid){ son[mid][0]=build(l,mid-1); fa[son[mid][0]]=mid; } if (r>mid){ son[mid][1]=build(mid+1,r); fa[son[mid][1]]=mid; } return(mid); }//建树时加入权值为0的0号点，权值为1的n+1号点，保证翻转l=1或r=n+1的操作正常进行 void rotate(int po,int s){ int f=fa[po]; pushdown(po); son[f][s]=son[po][s^1]; if (son[po][s^1]!=nil) fa[son[po][s^1]]=f; if (f==root) root=po;else if (f==son[fa[f]][0]) son[fa[f]][0]=po;else son[fa[f]][1]=po; fa[po]=fa[f]; fa[f]=po; son[po][s^1]=f; size[f]=size[son[f][0]]+size[son[f][1]]+v[f]; size[po]=size[son[po][0]]+size[son[po][1]]+v[po]; } void splay(int po,int targ){ while (fa[po]!=targ){ if (fa[fa[po]]==targ) {rotate(po,(po==son[fa[po]][1]));continue;} int u,v; if (po==son[fa[po]][1]) u=1;else u=-1; if (fa[po]==son[fa[fa[po]]][1]) v=1;else v=-1; if (u*v==1){ rotate(fa[po],(fa[po]==son[fa[fa[po]]][1])); rotate(po,(po==son[fa[po]][1])); }; if (u*v==-1){ rotate(po,(po==son[fa[po]][1])); rotate(po,(po==son[fa[po]][1])); } } size[po]=size[son[po][0]]+size[son[po][1]]+v[po]; } void reverse(int l,int r){ int p=find(l-1); splay(p,nil); p=find(r+1); splay(p,root); mark(son[son[root][1]][0]); } int main(){ freopen("a.in","r",stdin); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) v[i]=1; v[0]=0;v[n+1]=1; root=build(0,n+1); fa[root]=nil; for (int i=1;i<=m;i++){ int l,r; scanf("%d%d",&l,&r); reverse(l,r); } for (int i=1;i<=n;i++) printf("%d ",find(i)); }
区间翻转（BZOJ3223）
______________________________________________________________
#include <cstdio> const int nil=200000; int va[200001],b[200001],size[200001],son[200001][2],fa[200001],tmp[200001]; int root,n,m; int build(int l,int r){ int mid=(l+r)>>1; va[tmp[mid]]=mid; size[tmp[mid]]=(r-l+1); son[tmp[mid]][0]=son[tmp[mid]][1]=nil; if (l<mid) fa[son[tmp[mid]][0]=build(l,mid-1)]=tmp[mid]; if (r>mid) fa[son[tmp[mid]][1]=build(mid+1,r)]=tmp[mid]; return(tmp[mid]); } void update(int po){ size[po]=size[son[po][0]]+size[son[po][1]]+1; } void rotate(int po,int dir){ int so=son[po][dir]; son[po][dir]=son[so][dir^1]; if (son[so][dir^1]!=nil) fa[son[so][dir^1]]=po; fa[so]=fa[po]; if (fa[po]==nil) root=so;else if (po==son[fa[po]][0]) son[fa[po]][0]=so;else if (po==son[fa[po]][1]) son[fa[po]][1]=so; fa[po]=so; son[so][dir^1]=po; update(po); update(so); } void splay(int po,int tar){ if (fa[po]==tar) return; while (fa[po]!=tar){ if (fa[fa[po]]==tar) {rotate(fa[po],(po==son[fa[po]][1]));continue;} int u,v; if (po==son[fa[po]][1]) u=1;else u=-1; if (fa[po]==son[fa[fa[po]]][1]) v=1;else v=-1; if (u*v==1) rotate(fa[fa[po]],(po==son[fa[po]][1])),rotate(fa[po],(po==son[fa[po]][1])); if (u*v==-1) rotate(fa[po],(po==son[fa[po]][1])),rotate(fa[po],(po==son[fa[po]][1])); } update(po); } int rank(int po,int key){ int ret=0; if (va[po]==key) {ret=1+size[son[po][0]];splay(po,nil);return(ret);} if (va[po]<key) {if (son[po][0]!=nil) ret+=size[son[po][0]]; ret+=(rank(son[po][1],key)+1);} if (va[po]>key) ret+=rank(son[po][0],key); return(ret); } int kth(int po,int num){ if (num==size[son[po][0]]+1) {splay(po,nil);return(po);}; if (num>size[son[po][0]]+1) return(kth(son[po][1],num-size[son[po][0]]-1)); if (num<size[son[po][0]]+1) return(kth(son[po][0],num)); } void del(int po){ splay(po,nil); if (son[po][0]!=nil){ fa[son[po][0]]=nil; splay(root=kth(son[po][0],size[son[po][0]]),nil); son[root][1]=son[po][1]; fa[son[po][1]]=root; update(root); }else{ root=son[po][1];fa[son[po][1]]=nil; } fa[po]=nil;son[po][0]=son[po][1]=nil;size[po]=1; } void ins(int po){ int t=root; while (1){ if (va[t]>va[po]) {if (son[t][0]==nil) break; else t=son[t][0];}; if (va[t]<va[po]) {if (son[t][1]==nil) break; else t=son[t][1];}; continue; }; if (va[t]>va[po]) {son[t][0]=po;fa[po]=t;update(t);splay(po,nil);} if (va[t]<va[po]) {son[t][1]=po;fa[po]=t;update(t);splay(po,nil);} } int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++){ int t; scanf("%d",&t); b[t]=i; } for (int i=1;i<=n;i++) tmp[b[i]]=i; int topva,botva; fa[root=build(1,n)]=nil;topva=1;botva=n; char st[21]; for (int i=1;i<=m;i++){ scanf("%s",&st); int S,T; if (st[0]=='T') {scanf("%d ",&S);del(S);va[S]=--topva;ins(S);} if (st[0]=='B') {scanf("%d ",&S);del(S);va[S]=++botva;ins(S);} if (st[0]=='I') { scanf("%d",&S); scanf("%d",&T); if (T==0) continue; int po=kth(root,rank(root,va[S])+T); del(po); del(S); int t; t=va[po];va[po]=va[S];va[S]=t; ins(S);ins(po); } if (st[0]=='A') {scanf("%d ",&S);printf("%d ",rank(root,va[S])-1);} if (st[0]=='Q') {scanf("%d ",&S);printf("%d ",kth(root,S));} } }
单点操作 BZOJ1861(不包括删除全部点，在无点情况下插入)
----------------------------------------------
BZOJ2300结构体
#include <cstdio> #include <cmath> #include <algorithm> #define LDB long double using namespace std; int root,cnt,n,m,q; LDB ans=0; struct data{ int po,x,y; }a[400001]; struct treenode{ int po,son[2],fa,size; }tr[400001]; int ori[400001],cha[400001],b[400001],ccnt,que[400001],qcnt; LDB fin[400001]; int cmp(const data&a,const data&b){ if (a.x<b.x) return(1); if (a.x>b.x) return(0); return(a.y<b.y); } LDB dis(int x,int y){ return(sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y))); } void update(int po){ tr[po].size=tr[tr[po].son[0]].size+tr[tr[po].son[1]].size+1; } void rotate(int po,int dir){ int so=tr[po].son[dir]; tr[po].son[dir]=tr[so].son[dir^1]; if (tr[so].son[dir^1]) tr[tr[so].son[dir^1]].fa=po; tr[so].fa=tr[po].fa; if (tr[po].fa==0) root=so;else if (po==tr[tr[po].fa].son[0]) tr[tr[po].fa].son[0]=so;else if (po==tr[tr[po].fa].son[1]) tr[tr[po].fa].son[1]=so; tr[po].fa=so; tr[so].son[dir^1]=po; update(po); update(so); } void splay(int po,int tar){ if (tr[po].fa==tar) return; while (tr[po].fa!=tar){ if (tr[tr[po].fa].fa==tar) {rotate(tr[po].fa,(po==tr[tr[po].fa].son[1]));continue;} int u,v; if (po==tr[tr[po].fa].son[1]) u=1;else u=-1; if (tr[po].fa==tr[tr[tr[po].fa].fa].son[1]) v=1;else v=-1; if (u*v==1) rotate(tr[tr[po].fa].fa,(tr[po].fa==tr[tr[tr[po].fa].fa].son[1])),rotate(tr[po].fa,(po==tr[tr[po].fa].son[1])); if (u*v==-1) rotate(tr[po].fa,(po==tr[tr[po].fa].son[1])),rotate(tr[po].fa,(po==tr[tr[po].fa].son[1])); } update(po); } int getrank(int tar){ int po=root,ret=0; while (1){ if (tr[po].po==tar) {ret+=tr[tr[po].son[0]].size+1;splay(po,0);return(ret);} int dir=cmp(a[tr[po].po],a[tar]); if (dir){ ret+=tr[tr[po].son[1]].size+1;po=tr[po].son[1]; }else{ po=tr[po].son[0]; } } } int getkth(int po,int k){ while (1){ int lsum=tr[tr[po].son[0]].size; if (k==lsum+1){ splay(po,0); return(tr[po].po); }else if (k>lsum+1){ po=tr[po].son[1]; k-=lsum+1; }else{ po=tr[po].son[0]; } } } int getkth_node(int po,int k){ while (1){ int lsum=tr[tr[po].son[0]].size; if (k==lsum+1){ return(po); }else if (k>lsum+1){ po=tr[po].son[1]; k-=lsum+1; }else{ po=tr[po].son[0]; } } } void insert(int da){ int po=root; while(1){ tr[po].size++; int dir=cmp(a[tr[po].po],a[da]); if (tr[po].son[dir]) po=tr[po].son[dir];else{ tr[po].son[dir]=++cnt; tr[cnt].po=da; tr[cnt].fa=po; tr[cnt].size=1; po=tr[po].son[dir]; break; } } splay(po,0); } void del(int po){ splay(po,0); if (tr[root].son[1]){ int t=getkth_node(tr[root].son[1],1); splay(t,po); int t1=tr[po].son[0],t2=tr[po].son[1]; root=t2; tr[t2].fa=0;tr[t2].son[0]=t1;update(t2); tr[t1].fa=t2; }else tr[tr[root].son[0]].fa=0,root=tr[root].son[0]; } void push(int po){ insert(po); int k=getrank(po); if (k>1&&k<tr[root].size){ int chk1=getkth(root,k-1),chk2=getkth(root,k+1); LDB chky=0; if (a[chk1].x==a[chk2].x) chky=a[chk2].y;else chky=a[chk1].y+(a[chk2].y-a[chk1].y)*(a[po].x-a[chk1].x)/(LDB)(a[chk2].x-a[chk1].x); if (a[po].y<=chky){ del(cnt);return; } if (k>1&&k<tr[root].size) ans-=dis(chk1,chk2); } int t1,t2; t2=m+1; while (k>=3){ t1=getkth(root,k-2),t2=getkth(root,k-1); int x1=a[t2].x-a[t1].x,y1=a[t2].y-a[t1].y,x2=a[po].x-a[t2].x,y2=a[po].y-a[t2].y; if (x1*y2-x2*y1>0){ del(getkth_node(root,k-1)); ans-=dis(t1,t2); }else break; k--; } if (k>1) t2=getkth(root,k-1),ans+=dis(po,t2); t1=m+2; while (k<=tr[root].size-2){ t1=getkth(root,k+1),t2=getkth(root,k+2); int x1=a[t1].x-a[po].x,y1=a[t1].y-a[po].y,x2=a[t2].x-a[t1].x,y2=a[t2].y-a[t1].y; if (x1*y2-x2*y1>0){ del(getkth_node(root,k+1)); ans-=dis(t1,t2); }else break; } if (k<tr[root].size) t1=getkth(root,k+1),ans+=dis(po,t1); } int main(){ scanf("%d%d%d",&n,&a[0].x,&a[0].y);a[0].po=0; scanf("%d",&m); for (int i=1;i<=m;i++) scanf("%d%d",&a[i].x,&a[i].y),a[i].po=i; a[m+1].x=0;a[m+1].y=0;a[m+1].po=m+1;a[m+2].x=n;a[m+2].y=0;a[m+2].po=m+2; sort(a,a+m+1,cmp); for (int i=0;i<=m+2;i++) ori[a[i].po]=i; scanf("%d",&q); for (int i=1;i<=q;i++){ int opt; scanf("%d",&opt); if (opt==1){ scanf("%d",&cha[++ccnt]);b[cha[ccnt]]=1; }else{ que[++qcnt]=ccnt; } } root=++cnt; tr[cnt].po=ori[0];tr[cnt].size=1; for (int i=1;i<=m+2;i++) if (!b[i]) push(ori[i]); int po=qcnt; for (int i=ccnt;i>=0;i--){ while (que[po]==i&&po){ fin[po]=ans; po--; } if (i) push(ori[cha[i]]); } for (int i=1;i<=qcnt;i++) printf("%.2Lf ",fin[i]); }