题面：【模板】文艺平衡树（Splay）
题解：无
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<cstdlib> 5 using namespace std; 6 inline int rd(){ 7int x=0,f=1;char c=getchar(); 8while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();} 9while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}10return f*x;11 }12 const int maxn=(1e5)+50;13 int N,M,tot=0,val[maxn],siz[maxn],pr[maxn],rt=0,chd[maxn][3];14 int L,R,x,y,z;15 bool fl[maxn];16 inline int New_node(int a){17val[++tot]=a;18siz[tot]=1;19pr[tot]=rand();20return tot;21 }22 inline void Pushup(int a){23siz[a]=siz[chd[a][0]]+siz[chd[a][1]]+1;24return;25 }26 inline void Pushdown(int a){27if(fl[a]){28 swap(chd[a][0],chd[a][1]);29 if(chd[a][0])fl[chd[a][0]]^=1;30 if(chd[a][1])fl[chd[a][1]]^=1;31 fl[a]=0;32}33return;34 }35 inline int Merge(int a,int b){36if(!a||!b)return (a+b);37if(pr[a]<pr[b]){38 Pushdown(a);39 chd[a][1]=Merge(chd[a][1],b);40 Pushup(a);41 return a;42}43else{44 Pushdown(b);45 chd[b][0]=Merge(a,chd[b][0]);46 Pushup(b);47 return b;48}49 }50 inline void Split(int now,int k,int &x,int &y){51if(!now){x=y=0; return;}52Pushdown(now);53if(siz[chd[now][0]]+1<=k){54 x=now;55 Split(chd[now][1],k-siz[chd[now][0]]-1,chd[now][1],y);56}57else {58 y=now;59 Split(chd[now][0],k,x,chd[now][0]);60}61Pushup(now);62return;63 }64 inline void Work(int now){65if(!now)return;66Pushdown(now);67Work(chd[now][0]);68printf("%d ",val[now]);69Work(chd[now][1]);70return;71 }72 int main(){73srand(0304);74N=rd();M=rd();75for(int i=1;i<=N;i++)rt=Merge(rt,New_node(i));76while(M--){77 L=rd();R=rd();78 Split(rt,L-1,x,y);79 Split(y,R-L+1,y,z);80 fl[y]^=1;81 rt=Merge(Merge(x,y),z);82}83Work(rt);84return 0;85 }
By:AlenaNuna
