#include <cstdio>
#include <iostream>
using namespace std; const int nil=*1e5;//nil表示不存在的节点
int son[][],flag[],size[],v[];
int n,m;
int root,cnt,fa[]; inline void swap(int &a,int &b){
int t=a;
a=b;b=t;
} inline void mark(int po){
swap(son[po][],son[po][]);
flag[po]^=;
} inline void pushdown(int po){
int l=son[po][],r=son[po][];
if (flag[po]){
if (l!=nil) mark(l);
if (r!=nil) mark(r);
flag[po]^=;
}
} inline int find(int num){
int po=root;
while (){
pushdown(po);
if (size[son[po][]]+v[po]==num) {return(po);continue;}
if (size[son[po][]]+v[po]>num) {po=son[po][];continue;}
if (size[son[po][]]+v[po]<num) {num-=size[son[po][]]+v[po],po=son[po][];continue;}
}
} int build(int l,int r){
int mid=(l+r)>>;
size[mid]=min(r,n)-max(l,)+;
son[mid][]=son[mid][]=nil; if (l<mid){
son[mid][]=build(l,mid-);
fa[son[mid][]]=mid;
} if (r>mid){
son[mid][]=build(mid+,r);
fa[son[mid][]]=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^];
if (son[po][s^]!=nil) fa[son[po][s^]]=f;
if (f==root) root=po;else
if (f==son[fa[f]][]) son[fa[f]][]=po;else
son[fa[f]][]=po;
fa[po]=fa[f];
fa[f]=po;
son[po][s^]=f;
size[f]=size[son[f][]]+size[son[f][]]+v[f];
size[po]=size[son[po][]]+size[son[po][]]+v[po];
} void splay(int po,int targ){
while (fa[po]!=targ){
if (fa[fa[po]]==targ) {rotate(po,(po==son[fa[po]][]));continue;}
int u,v;
if (po==son[fa[po]][]) u=;else u=-;
if (fa[po]==son[fa[fa[po]]][]) v=;else v=-;
if (u*v==){
rotate(fa[po],(fa[po]==son[fa[fa[po]]][]));
rotate(po,(po==son[fa[po]][]));
};
if (u*v==-){
rotate(po,(po==son[fa[po]][]));
rotate(po,(po==son[fa[po]][]));
}
}
size[po]=size[son[po][]]+size[son[po][]]+v[po];
} void reverse(int l,int r){
int p=find(l-);
splay(p,nil);
p=find(r+);
splay(p,root);
mark(son[son[root][]][]);
} int main(){
freopen("a.in","r",stdin); scanf("%d%d",&n,&m); for (int i=;i<=n;i++) v[i]=;
v[]=;v[n+]=;
root=build(,n+);
fa[root]=nil; for (int i=;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
reverse(l,r);
} for (int i=;i<=n;i++) printf("%d ",find(i));
}
区间翻转（BZOJ3223）
______________________________________________________________
#include <cstdio> const int nil=;
int va[],b[],size[],son[][],fa[],tmp[];
int root,n,m; int build(int l,int r){
int mid=(l+r)>>;
va[tmp[mid]]=mid;
size[tmp[mid]]=(r-l+);
son[tmp[mid]][]=son[tmp[mid]][]=nil; if (l<mid) fa[son[tmp[mid]][]=build(l,mid-)]=tmp[mid];
if (r>mid) fa[son[tmp[mid]][]=build(mid+,r)]=tmp[mid];
return(tmp[mid]);
} void update(int po){
size[po]=size[son[po][]]+size[son[po][]]+;
} void rotate(int po,int dir){
int so=son[po][dir];
son[po][dir]=son[so][dir^];
if (son[so][dir^]!=nil) fa[son[so][dir^]]=po;
fa[so]=fa[po];
if (fa[po]==nil) root=so;else
if (po==son[fa[po]][]) son[fa[po]][]=so;else
if (po==son[fa[po]][]) son[fa[po]][]=so;
fa[po]=so;
son[so][dir^]=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]][]));continue;}
int u,v;
if (po==son[fa[po]][]) u=;else u=-;
if (fa[po]==son[fa[fa[po]]][]) v=;else v=-;
if (u*v==) rotate(fa[fa[po]],(po==son[fa[po]][])),rotate(fa[po],(po==son[fa[po]][]));
if (u*v==-) rotate(fa[po],(po==son[fa[po]][])),rotate(fa[po],(po==son[fa[po]][]));
}
update(po);
} int rank(int po,int key){
int ret=;
if (va[po]==key) {ret=+size[son[po][]];splay(po,nil);return(ret);}
if (va[po]<key) {if (son[po][]!=nil) ret+=size[son[po][]];
ret+=(rank(son[po][],key)+);}
if (va[po]>key) ret+=rank(son[po][],key);
return(ret);
} int kth(int po,int num){
if (num==size[son[po][]]+) {splay(po,nil);return(po);};
if (num>size[son[po][]]+) return(kth(son[po][],num-size[son[po][]]-));
if (num<size[son[po][]]+) return(kth(son[po][],num));
} void del(int po){
splay(po,nil);
if (son[po][]!=nil){
fa[son[po][]]=nil;
splay(root=kth(son[po][],size[son[po][]]),nil);
son[root][]=son[po][];
fa[son[po][]]=root;
update(root);
}else{
root=son[po][];fa[son[po][]]=nil;
}
fa[po]=nil;son[po][]=son[po][]=nil;size[po]=;
} void ins(int po){
int t=root;
while (){
if (va[t]>va[po])
{if (son[t][]==nil) break;
else t=son[t][];};
if (va[t]<va[po])
{if (son[t][]==nil) break;
else t=son[t][];};
continue;
};
if (va[t]>va[po]) {son[t][]=po;fa[po]=t;update(t);splay(po,nil);}
if (va[t]<va[po]) {son[t][]=po;fa[po]=t;update(t);splay(po,nil);}
} int main(){
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++){
int t;
scanf("%d",&t);
b[t]=i;
}
for (int i=;i<=n;i++) tmp[b[i]]=i; int topva,botva;
fa[root=build(,n)]=nil;topva=;botva=n; char st[];
for (int i=;i<=m;i++){
scanf("%s",&st);
int S,T;
if (st[]=='T') {scanf("%d\n",&S);del(S);va[S]=--topva;ins(S);}
if (st[]=='B') {scanf("%d\n",&S);del(S);va[S]=++botva;ins(S);}
if (st[]=='I') {
scanf("%d",&S);
scanf("%d",&T);
if (T==) 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[]=='A') {scanf("%d\n",&S);printf("%d\n",rank(root,va[S])-);}
if (st[]=='Q') {scanf("%d\n",&S);printf("%d\n",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=; struct data{
int po,x,y;
}a[]; struct treenode{
int po,son[],fa,size;
}tr[]; int ori[],cha[],b[],ccnt,que[],qcnt;
LDB fin[]; int cmp(const data&a,const data&b){
if (a.x<b.x) return();
if (a.x>b.x) return();
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[]].size+tr[tr[po].son[]].size+;
} void rotate(int po,int dir){
int so=tr[po].son[dir];
tr[po].son[dir]=tr[so].son[dir^];
if (tr[so].son[dir^]) tr[tr[so].son[dir^]].fa=po;
tr[so].fa=tr[po].fa;
if (tr[po].fa==) root=so;else
if (po==tr[tr[po].fa].son[]) tr[tr[po].fa].son[]=so;else
if (po==tr[tr[po].fa].son[]) tr[tr[po].fa].son[]=so;
tr[po].fa=so;
tr[so].son[dir^]=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[]));continue;}
int u,v;
if (po==tr[tr[po].fa].son[]) u=;else u=-;
if (tr[po].fa==tr[tr[tr[po].fa].fa].son[]) v=;else v=-;
if (u*v==) rotate(tr[tr[po].fa].fa,(tr[po].fa==tr[tr[tr[po].fa].fa].son[])),rotate(tr[po].fa,(po==tr[tr[po].fa].son[]));
if (u*v==-) rotate(tr[po].fa,(po==tr[tr[po].fa].son[])),rotate(tr[po].fa,(po==tr[tr[po].fa].son[]));
}
update(po);
} int getrank(int tar){
int po=root,ret=;
while (){
if (tr[po].po==tar) {ret+=tr[tr[po].son[]].size+;splay(po,);return(ret);}
int dir=cmp(a[tr[po].po],a[tar]);
if (dir){
ret+=tr[tr[po].son[]].size+;po=tr[po].son[];
}else{
po=tr[po].son[];
}
}
} int getkth(int po,int k){
while (){
int lsum=tr[tr[po].son[]].size;
if (k==lsum+){
splay(po,);
return(tr[po].po);
}else
if (k>lsum+){
po=tr[po].son[];
k-=lsum+;
}else{
po=tr[po].son[];
}
}
} int getkth_node(int po,int k){
while (){
int lsum=tr[tr[po].son[]].size;
if (k==lsum+){
return(po);
}else
if (k>lsum+){
po=tr[po].son[];
k-=lsum+;
}else{
po=tr[po].son[];
}
}
} void insert(int da){
int po=root;
while(){
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=;
po=tr[po].son[dir];
break;
}
}
splay(po,);
} void del(int po){
splay(po,);
if (tr[root].son[]){
int t=getkth_node(tr[root].son[],);
splay(t,po);
int t1=tr[po].son[],t2=tr[po].son[];
root=t2;
tr[t2].fa=;tr[t2].son[]=t1;update(t2);
tr[t1].fa=t2;
}else tr[tr[root].son[]].fa=,root=tr[root].son[];
} void push(int po){
insert(po);
int k=getrank(po);
if (k>&&k<tr[root].size){
int chk1=getkth(root,k-),chk2=getkth(root,k+);
LDB chky=;
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>&&k<tr[root].size) ans-=dis(chk1,chk2);
}
int t1,t2;
t2=m+;
while (k>=){
t1=getkth(root,k-),t2=getkth(root,k-);
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>){
del(getkth_node(root,k-));
ans-=dis(t1,t2);
}else break;
k--;
}
if (k>) t2=getkth(root,k-),ans+=dis(po,t2);
t1=m+;
while (k<=tr[root].size-){
t1=getkth(root,k+),t2=getkth(root,k+);
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>){
del(getkth_node(root,k+));
ans-=dis(t1,t2);
}else break;
}
if (k<tr[root].size) t1=getkth(root,k+),ans+=dis(po,t1);
} int main(){
scanf("%d%d%d",&n,&a[].x,&a[].y);a[].po=; scanf("%d",&m);
for (int i=;i<=m;i++)
scanf("%d%d",&a[i].x,&a[i].y),a[i].po=i;
a[m+].x=;a[m+].y=;a[m+].po=m+;a[m+].x=n;a[m+].y=;a[m+].po=m+;
sort(a,a+m+,cmp);
for (int i=;i<=m+;i++)
ori[a[i].po]=i; scanf("%d",&q);
for (int i=;i<=q;i++){
int opt;
scanf("%d",&opt);
if (opt==){
scanf("%d",&cha[++ccnt]);b[cha[ccnt]]=;
}else{
que[++qcnt]=ccnt;
}
} root=++cnt;
tr[cnt].po=ori[];tr[cnt].size=;
for (int i=;i<=m+;i++)
if (!b[i])
push(ori[i]); int po=qcnt;
for (int i=ccnt;i>=;i--){
while (que[po]==i&&po){
fin[po]=ans;
po--;
}
if (i) push(ori[cha[i]]);
} for (int i=;i<=qcnt;i++) printf("%.2Lf\n",fin[i]);
}