在比较了网上的几份模板的速度之后，发现指针版明显快了很多，但是一敲起来。。。。各种不习惯。。。所以还是学的hzwer 的数组版。。。

bzoj3223：维护reverse操作就可以了

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))int read(){	int x=0;char c=getchar();	while(!isdigit(c)) c=getchar();	while(isdigit(c)) x=x*10+c-'0',c=getchar();	return x;}const int nmax=1e5+5;const int inf=0x7f7f7f7f;int fa[nmax],c[nmax][2],sz[nmax],rev[nmax],n,m,rt;void pushup(int x){	sz[x]=sz[c[x][0]]+sz[c[x][1]]+1;}void build(int l,int r,int last){	if(l>r) return ;	if(l==r){		fa[l]=last,sz[l]=1,c[last][l>=last]=l;return ;	}	int mid=(l+r)>>1;	build(l,mid-1,mid);build(mid+1,r,mid);	fa[mid]=last;c[last][l>=last]=mid;pushup(mid);}void rotate(int x,int &k){	int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;	if(y==k) k=x;	else c[z][c[z][1]==y]=x;	fa[x]=z;fa[y]=x;fa[c[x][r]]=y;	c[y][l]=c[x][r];c[x][r]=y;	pushup(y);pushup(x);}void splay(int x,int &k){	int y,z;	while(x!=k){		y=fa[x],z=fa[y];		if(y!=k){			if(c[y][0]==x^c[z][0]==y) rotate(x,k);			else rotate(y,k);		}		rotate(x,k);	}}void pushdown(int x){	if(rev[x]){		int l=c[x][0],r=c[x][1];		rev[x]=0;rev[l]^=1;rev[r]^=1;		swap(c[x][0],c[x][1]);	}}int find(int x,int rk){	pushdown(x);	int l=c[x][0],r=c[x][1];	if(sz[l]+1==rk) return x;	if(sz[l]>=rk) return find(l,rk);	return find(r,rk-sz[l]-1);}void rever(int l,int r){	int x=find(rt,l),y=find(rt,r+2);	splay(x,rt);splay(y,c[x][1]);	rev[c[y][0]]^=1;}int main(){	n=read(),m=read();	build(1,n+2,0);rt=(n+3)>>1;	int u,v,d,tmp,temp;	rep(i,1,m) u=read(),v=read(),rever(u,v);	rep(i,2,n+1) printf("%d ",find(rt,i)-1);	return 0;}/*5 31 31 31 4*/
        
       
      
     

 bzoj1251：维护reverse，query，update操作就可以了。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))int read(){	int x=0,f=1;char c=getchar();	while(!isdigit(c)){		if(c=='-') f=-1;c=getchar();	}	while(isdigit(c)) x=x*10+c-'0',c=getchar();	return x*f;}const int nmax=5e4+5;const int inf=0x7f7f7f7f;int fa[nmax],c[nmax][2],id[nmax],tag[nmax],w[nmax],mx[nmax],sz[nmax],n,m,rt;bool rev[nmax];void pushup(int x){	int l=c[x][0],r=c[x][1];	mx[x]=max(w[x],max(mx[l],mx[r]));	sz[x]=sz[l]+sz[r]+1;}void build(int l,int r,int last){	if(l>r) return ;	if(l==r){		fa[l]=last;sz[l]=1;		c[last][l>=last]=l;return ;	}	int mid=(l+r)>>1,now=mid;	build(l,mid-1,mid);build(mid+1,r,mid);	fa[now]=last;c[last][l>=last]=now;pushup(now);}void rotate(int x,int &k){	int y=fa[x],z=fa[y],l=(c[y][1]==x),r=l^1;	if(y==k) k=x;else c[z][c[z][1]==y]=x;	fa[x]=z;fa[y]=x;fa[c[x][r]]=y;	c[y][l]=c[x][r];c[x][r]=y;	pushup(y);pushup(x);}void splay(int x,int &k){	int y,z;	while(x!=k){		y=fa[x];z=fa[y];		if(y!=k){			if(c[y][0]==x^c[z][0]==y) rotate(x,k);			else rotate(y,k);		}		rotate(x,k);	}}void pushdown(int x){	int l=c[x][0],r=c[x][1],t=tag[x];	if(t){		tag[x]=0;		if(l) tag[l]+=t,mx[l]+=t,w[l]+=t;		if(r) tag[r]+=t,mx[r]+=t,w[r]+=t;	}	if(rev[x]){		rev[x]=0;rev[l]^=1;rev[r]^=1;		swap(c[x][0],c[x][1]);	}}int find(int x,int rk){	pushdown(x);	int l=c[x][0],r=c[x][1];	if(sz[l]+1==rk) return x;	if(sz[l]>=rk) return find(l,rk);	return find(r,rk-sz[l]-1);}void update(int l,int r,int val){	int x=find(rt,l),y=find(rt,r+2);	splay(x,rt);splay(y,c[x][1]);	int z=c[y][0];	tag[z]+=val,w[z]+=val,mx[z]+=val;}void rever(int l,int r){	int x=find(rt,l),y=find(rt,r+2);	splay(x,rt);splay(y,c[x][1]);	rev[c[y][0]]^=1;}void query(int l,int r){	int x=find(rt,l),y=find(rt,r+2);	splay(x,rt);splay(y,c[x][1]);	printf("%d\n",mx[c[y][0]]);}int main(){	n=read(),m=read();	rep(i,1,n+2) id[i]=i;	mx[0]=-inf;build(1,n+2,0);rt=(n+3)>>1;	int u,v,d,tmp,temp;	rep(i,1,m){		u=read();		if(u==1) v=read(),d=read(),tmp=read(),update(v,d,tmp);		else if(u==2) v=read(),d=read(),rever(v,d);		else v=read(),d=read(),query(v,d);	}	return 0;}
        
       
      
     

bzoj1588:维护insert，ask_before ,ask_after 操作即可

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))int read(){	int x=0,f=1;char c=getchar();	while(!isdigit(c)){		if(c=='-') f=-1;c=getchar();	}	while(isdigit(c)) x=x*10+c-'0',c=getchar();	return x*f;}const int nmax=5e4+5;const int inf=1e9;int c[nmax][2],fa[nmax],w[nmax],sz,rt;void rotate(int x,int &k){	int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;	if(y==k) k=x;else c[z][c[z][1]==y]=x;	fa[x]=z;fa[y]=x;fa[c[x][r]]=y;	c[y][l]=c[x][r];c[x][r]=y;}void splay(int x,int &k){	int y,z;	while(x!=k){		y=fa[x];z=fa[y];		if(y!=k){			if(c[y][0]==x^c[z][0]==y) rotate(x,k);			else rotate(y,k);		}		rotate(x,k);	}}void insert(int &k,int x,int last){	if(!k) {		k=++sz;w[k]=x;fa[k]=last;splay(k,rt);	}else if(x
         
          =x) ans=w[t],t=c[t][0];		else t=c[t][1];	}	return ans;}int main(){	int n=read(),ans=0;insert(rt,inf,0);insert(rt,-inf,0);	rep(i,1,n){		int u=read(),ta=ask_before(u),tb=ask_after(u);		if(i!=1) ans+=min(u-ta,tb-u);else ans+=u;		insert(rt,u,0);	}	printf("%d\n",ans);	return 0;}