模板保存。
#include<iostream> #include<cstdio> #include<cstring> #include<ctime> #include<cstdlib> #include<cmath> #include<algorithm> #define maxn 500001 using namespace std; typedef long long ll; int size[maxn],ch[maxn][2],rnd[maxn],val[maxn],rev[maxn]; int ncnt,x,y,z,rt,n,m; inline void pushup(int x){ size[x]=1+size[ch[x][0]]+size[ch[x][1]]; } inline void pushdown(int rt){ if(rev[rt]){ swap(ch[rt][0],ch[rt][1]); if(ch[rt][0]) rev[ch[rt][0]]^=1; if(ch[rt][1]) rev[ch[rt][1]]^=1; rev[rt]=0; } } inline int new_node(int x){ size[++ncnt]=1; val[ncnt]=x; rnd[ncnt]=rand(); return ncnt; } //核心 int merge(int A,int B){ if(!A||!B) return A+B; if(rnd[A]<rnd[B]){pushdown(A);ch[A][1]=merge(ch[A][1],B);pushup(A);return A;} else {pushdown(B);ch[B][0]=merge(A,ch[B][0]);pushup(B);return B;} } //权值分裂 void split_1(int now,int k,int &x,int &y){ if(!now) x=y=0; else{ pushdown(now); if(val[now]<=k) x=now,split_1(ch[now][1],k,ch[now][1],y); else y=now,split_1(ch[now][0],k,x,ch[now][0]); pushup(now); } } //排名分裂 void split_2(int now,int k,int &x,int &y){ if(!now) x=y=0; else{ pushdown(now); if(k<=size[ch[now][0]]){y=now;split_2(ch[now][0],k,x,ch[now][0]);} else{x=now;split_2(ch[now][1],k-size[ch[now][0]]-1,ch[now][1],y);} pushup(now); } } void insert(int &k,int a){ split_1(k,a,x,y); k=merge(merge(x,new_node(a)),y); } //会浪费空间,没有回收节点 void del(int &k,int a){ split_1(k,a,x,z); split_1(x,a-1,x,y); y=merge(ch[y][0],ch[y][1]); k=merge(merge(x,y),z); } int rnk(int &k,int a){ split_1(k,a-1,x,y); int res=size[x]+1; k=merge(x,y); return res; } int kth(int now,int k){ while(1){ if(k<=size[ch[now][0]]) now=ch[now][0]; else if(k==size[ch[now][0]]+1) return val[now]; else k-=size[ch[now][0]]+1,now=ch[now][1]; } } int pred(int &k,int a){ split_1(k,a-1,x,y); int res=kth(x,size[x]); k=merge(x,y); return res; } int succ(int &k,int a){ split_1(k,a,x,y); int res=kth(y,1); k=merge(x,y); return res; } void reverse(int &k,int l,int r){ split_2(k,l-1,x,y); split_2(y,r-l+1,y,z); rev[y]^=1; k=merge(x,merge(y,z)); } void print(int &k){ if(!k) return; pushdown(k); print(ch[k][0]); if(val[k]>=1&&val[k]<=n) printf("%d ",val[k]); print(ch[k][1]); } int main(){ srand(time(0)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) insert(rt,i); for(int i=1,l,r;i<=m;i++){ scanf("%d%d",&l,&r); reverse(rt,l,r); } print(rt); return 0; }