P3391 文艺平衡树（Splay区间翻转）

题解：

Splay区间反转的模板题。

翻转[3,5]时，我们可以将3的前驱找到，5的后继找到，然后根节点的右儿子的左子树就是属于[3,5]这个区间的数，可以自己画画就容易知道了。

然后就是给这个结点打上标记表示这个区间是需要翻转的，在以后查询或者需要时就标记下放，左右子树翻转即可。

AC代码：

#include<bits/stdc++.h>using namespace std;typedef long long LL;const int MAXN = 1e5+10;const int MOD = 998244353;struct node{int son[2],fa,val,sz,lazy;void init(int f,int v){fa=f; val=v; sz=1; }}t[MAXN];int root,tot,n,m,a[MAXN];inline int id(int x){return x==t[t[x].fa].son[1]; }inline void pushup(int x){t[x].sz = t[t[x].son[0]].sz+t[t[x].son[1]].sz+1;}inline void pushdown(int x){if(t[x].lazy){t[t[x].son[0]].lazy ^= 1;t[t[x].son[1]].lazy ^= 1;t[x].lazy = 0;swap(t[x].son[0],t[x].son[1]);}}inline void rotate(int x){int y=t[x].fa,z=t[y].fa,k=id(x);t[z].son[id(y)]=x; t[x].fa=z;t[y].son[k]=t[x].son[k^1]; t[t[x].son[k^1]].fa=y;t[x].son[k^1]=y; t[y].fa=x;pushup(y); pushup(x);}inline void splay(int x,int pos){while(t[x].fa!=pos){int y=t[x].fa,z=t[y].fa;if(z!=pos) id(x)==id(y) ? rotate(y):rotate(x);rotate(x);}if(!pos) root=x;}inline int build(int rt,int l,int r){if(l>r) return 0; int mid=(l+r)>>1;int u=++tot;t[u].init(rt,a[mid]);t[u].son[0]=build(u,l,mid-1);t[u].son[1]=build(u,mid+1,r);pushup(u); return u;}inline int kth(int x){int u=root;while(1){pushdown(u);if(t[t[u].son[0]].sz>=x) u=t[u].son[0];else{x -= t[t[u].son[0]].sz+1;if(!x) return u;u = t[u].son[1];}}}void dfs(int u){pushdown(u);if(t[u].son[0]) dfs(t[u].son[0]);if(t[u].val>=1 && t[u].val<=n) printf("%d ",t[u].val);if(t[u].son[1]) dfs(t[u].son[1]);}signed main(){#ifndef ONLINE_JUDGEfreopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);#endif // ONLINE_JUDGEscanf("%d%d",&n,&m); a[1]=-1e9; a[n+2]=1e9;for(int i=2;i<=n+1;i++) a[i]=i-1;root = build(0,1,n+2);while(m--){int l,r; scanf("%d%d",&l,&r);int ll=kth(l),rr=kth(r+2);splay(ll,0); splay(rr,ll);t[t[t[root].son[1]].son[0]].lazy ^= 1;}dfs(root);return 0;}

AC代码：

#include<bits/stdc++.h>using namespace std;typedef long long LL;const int MAXN = 1e5+10;const int MOD = 998244353;struct node{int son[2],fa,val,sz,lazy;void init(int f,int v){fa=f; val=v; sz=1; }}t[MAXN];int root,tot,n,m;inline int id(int x){return x==t[t[x].fa].son[1]; }inline void pushup(int x){t[x].sz = t[t[x].son[0]].sz+t[t[x].son[1]].sz+1;}inline void pushdown(int x){if(t[x].lazy){t[t[x].son[0]].lazy ^= 1;t[t[x].son[1]].lazy ^= 1;t[x].lazy = 0;swap(t[x].son[0],t[x].son[1]);}}inline void rotate(int x){int y=t[x].fa,z=t[y].fa,k=id(x);t[z].son[id(y)]=x; t[x].fa=z;t[y].son[k]=t[x].son[k^1]; t[t[x].son[k^1]].fa=y;t[x].son[k^1]=y; t[y].fa=x;pushup(y); pushup(x);}inline void splay(int x,int pos){while(t[x].fa!=pos){int y=t[x].fa,z=t[y].fa;if(z!=pos) id(x)==id(y) ? rotate(y):rotate(x);rotate(x);}if(!pos) root=x;}inline void Insert(int x){int u=root,fa=0;while(u) fa=u,u=t[u].son[x>t[u].val];u=++tot;if(fa) t[fa].son[x>t[fa].val]=u;t[u].init(fa,x);splay(u,0);}inline int kth(int x){int u=root;while(1){pushdown(u);if(t[t[u].son[0]].sz>=x) u=t[u].son[0];else{x -= t[t[u].son[0]].sz+1;if(!x) return u;u = t[u].son[1];}}}void dfs(int u){pushdown(u);if(t[u].son[0]) dfs(t[u].son[0]);if(t[u].val>=2 && t[u].val<=n+1) printf("%d ",t[u].val-1);if(t[u].son[1]) dfs(t[u].son[1]);}signed main(){#ifndef ONLINE_JUDGEfreopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);#endif // ONLINE_JUDGEscanf("%d%d",&n,&m);for(int i=1;i<=n+2;i++) Insert(i);while(m--){int l,r; scanf("%d%d",&l,&r);int ll=kth(l),rr=kth(r+2);splay(ll,0); splay(rr,ll);t[t[t[root].son[1]].son[0]].lazy ^= 1;}dfs(root);return 0;}