bzoj3223：Tyvj 1729 文藝平衡樹

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

題解

splay模版題，比較能展現splay優勢的就是區間性的問題了吧。

splay，顧名思義，往死玩。。比較騷的操作就是旋轉，利用異或實作，了解難度和treap差不多？？

1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define maxn 100005
 5 using namespace std;
 6 int n,m,root;
 7 struct Splay{
 8     int c[2],fa,siz;
 9     bool rev;
10 }a[maxn];
11 void pushup(int o){a[o].siz=a[a[o].c[0]].siz+a[a[o].c[1]].siz+1;}
12 void reserve(int o)
13 {
14     if(!o)return ;
15     swap(a[o].c[0],a[o].c[1]);
16     a[o].rev^=1;
17     return ;
18 }
19 void pushdown(int o)
20 {
21     if(a[o].rev)
22     {
23         reserve(a[o].c[0]);
24         reserve(a[o].c[1]);
25         a[o].rev=false;
26         return ;
27     }
28 }
29 void rotate(int &o,int x)
30 {
31     int y=a[x].fa,z=a[y].fa,dy=a[y].c[1]==x,dz=a[z].c[1]==y;
32     pushdown(y);
33     if(o==y)o=x;
34     else a[z].c[dz]=x;
35     a[x].fa=z;
36     a[y].c[dy]=a[x].c[dy^1];
37     a[a[y].c[dy]].fa=y;
38     a[x].c[dy^1]=y;
39     a[y].fa=x;
40     pushup(y);
41     return ;
42 }
43 void splay(int &o,int x)
44 {
45     pushdown(x);
46     while(o!=x)
47     {    
48         int y=a[x].fa,z=a[y].fa;
49         if(o!=y)
50         {
51             if(x==a[y].c[1]^y==a[z].c[1])rotate(o,x);
52             else rotate(o,y);
53         }
54         rotate(o,x);
55     }
56     pushup(x);
57     return ;
58 }
59 int find(int o,int x)
60 {
61     pushdown(o);
62     if(x<=a[a[o].c[0]].siz)return find(a[o].c[0],x);
63     if(x<=a[a[o].c[0]].siz+1)return o;
64     return find(a[o].c[1],x-1-a[a[o].c[0]].siz);
65 }
66 void print(int o)
67 {
68     if(!o)return ;
69     pushdown(o);
70     print(a[o].c[0]);
71     if(o>1&&o<n+2)printf("%d ",o-1);
72     print(a[o].c[1]);
73     return ;
74 }
75 int main()
76 {
77     scanf("%d%d",&n,&m);
78     a[1].siz=n+2;a[1].c[1]=2;
79     a[n+2].siz=1;a[n+2].fa=n+1;
80     for(int i=1 ; i<=n ; ++i)a[i+1]=(Splay){{0,i+2},i,n+2-i,false};
81     root=1;
82     for(int i=1 ; i<=m ; ++i )
83     {
84         int l,r;
85         scanf("%d%d",&l,&r);
86         r+=2;
87         l=find(root,l);r=find(root,r);
88         splay(root,l);splay(a[root].c[1],r);
89         reserve(a[r].c[0]);
90     }
91     print(root);
92     return 0;
93 }      

轉載于:https://www.cnblogs.com/fujudge/p/7554970.html