題目
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)
