题目
3223: Tyvj 1729 文艺平衡树 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1212 Solved: 639 [Submit][Status] Description 您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1 Input 第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数 接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n Output
输出一行n个数字，表示原始序列经过m次变换后的结果 Sample Input 5 3
1 3
1 3
1 4
Sample Output 4 3 2 1 5
HINT
N,M<=100000
Source 平衡树
题解
首先我们考虑一下怎么样把[l,r]这一段弄到一起 可以发现如果我们把l-1splay到根,r+1splay到根的右儿子，那么r+1节点的左子树就是区间[l,r]了 这里为了方便处理（其实是懒得特判l=1和r=n的情况QAQ）我们可以新建两个虚点来维护这一棵树 然后如果直接转好像很慢耶 所以我们可以打下标记，每次splay里面有关系到两个点的位置变换的操作之前或者是在做kth时经过某个点就旋转 根据平衡树的性质我们如果给x打了标记，那么x的子树怎么转都是没有影响的，所以这样做的正确性显然 最后我们再从根开始做一次dfs来把剩下的lazy给处理了（好像可以和输出答案的dfs一起做哦~）
需要注意的是 1：pushdown操作要放在splay里而不是rotate里（其实我无法理解网上很多标在rotate里面做pushdown，有这样的情况：x一开始为y的左儿子，此时要对x进行右旋，但是我在旋转之前进行了一次pushdown，那我的x就变成了y的右儿子，这样会导致rotate里后面的操作出现问题，与其在rotate里又打一堆东西还不如在splay里就转过来） 2：在kth里面也要转 看了下网上的标很多都没有在这里pushdown到底是什么情况？如果在这里不旋转会影响到pushdown最后的返回值的，原因十分显然吧QvQ
贴代码
#include<iostream>#include<algorithm>#include<stdio.h>#include<string.h>#include<math.h>using namespace std;const int maxn=100005;int data[maxn],father[maxn],cnt[maxn],lazy[maxn];int son[maxn][3];int i,j,k,l,n,m,t1,t2,root,x,y;void pushdown(int x){ int y; if (!lazy[x]) return; y=son[x][1]; son[x][1]=son[x][2]; son[x][2]=y; if (son[x][1]) lazy[son[x][1]]^=1; if (son[x][2]) lazy[son[x][2]]^=1; lazy[x]=0;}void rotate(int x,int w){ int y; y=father[x]; cnt[y]=cnt[y]-cnt[x]+cnt[son[x][w]]; cnt[x]=cnt[x]+cnt[y]-cnt[son[x][w]]; father[x]=father[y]; if (father[y]){ if (son[father[y]][1]==y) son[father[y]][1]=x; else son[father[y]][2]=x; } son[y][3-w]=son[x][w]; if (son[x][w]) father[son[x][w]]=y; father[y]=x; son[x][w]=y;}void splay(int x){ int y; pushdown(x); while (father[x]){ y=father[x]; if (!father[y]) pushdown(father[y]); pushdown(y); pushdown(x); if (y==root){ if (son[y][1]==x) rotate(x,2); else rotate(x,1); } else{ if (y==son[father[y]][1]){ if (son[y][1]==x) {rotate(y,2); rotate(x,2);} else{rotate(x,1); rotate(x,2);} } else{ if (son[y][1]==x){rotate(x,2); rotate(x,1);} else{rotate(y,1); rotate(x,1);} } } } root=x;}int kth(int x,int w){ int i; int tmp; tmp=x; i=root; pushdown(i); while ((x!=cnt[son[i][w]]+1) && (i)){ if (x<cnt[son[i][w]]+1) i=son[i][w]; else{ x=x-cnt[son[i][w]]-1; i=son[i][3-w]; } pushdown(i); } splay(i); return i;}void dfs(int x){ pushdown(x); if (son[x][1]) dfs(son[x][1]); if (son[x][2]) dfs(son[x][2]);}void makeans(int x){ if (son[x][1]) makeans(son[x][1]); if (data[x]) if (data[x]!=n+1) PRintf("%d ",data[x]); if (son[x][2]) makeans(son[x][2]);}int main(){ //freopen("3223.in","r",stdin); //freopen("3223.out","w",stdout); scanf("%d%d",&n,&m); for (i=2;i<=n+2;i++){ data[i]=i-1; father[i]=i-1; son[i-1][2]=i; cnt[i]=n-i+3; } cnt[1]=n+2; root=1; for (i=1;i<=m;i++){ scanf("%d%d",&t1,&t2); t2++; x=kth(t1,1); father[son[root][2]]=0; y=cnt[son[root][1]]; root=son[root][2]; l=kth(t2-y,1); father[l]=x; son[x][2]=l; root=x; lazy[son[l][1]]^=1; } dfs(root); makeans(root); return 0;}
