天天看點
傳回

BZOJ 3223 Tyvj 1729 文藝平衡樹

3223: 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，實在是調了太久太久。

　　不過至少調出來了嘛！☺

　　就是最普通的平衡樹，而且此題還不用insert和remove。是以，就是build，splay，merge和split，再加上rev标記和pushdown。splay的cmp與treap的cmp不同，treap的cmp是按值的，而splay是按siz的（因為是下标标号）。是以說，insert的時候有k還有x（x似乎無用）。額，似乎很顯然。而進入ch[1]的時候，一定不能忘了先把k減下去。

　　關于splay操作，按理是雙旋的，但我寫了随機比較單旋和雙旋，似乎沒有什麼大差別。事實似乎也是這樣。

splay單旋 2776 kb 2184 ms 2351 B
splay雙旋 2776 kb 2004 ms 2559 B

　　但是，确實有理論證明。雙旋可以有效地“本質化地”優化樹的形态。

　　關于split和merge，劉汝佳建議，使用虛拟節點，但本人嫌麻煩，隻需要再特判一下。因為split是把樹o的前k個分入left，之後的分入right，當k為0時就不用旋也不能旋了。而且merge是把left變成“右空樹”再連上 right，當left為null時就不用旋也不能旋了。第一次感覺null這麼友善。

　　而rev标記，是隻要通路就該pushdown了，無論是insert，remove，還是splay，print，如果忘了會出大事。

　　而maintain（update）呢？隻要樹形态變化就應該做。也就是build，insert，remove，rotate，還有merge和split。注意splay内部并不需要maintain，因為splay本身不過是一堆rotate。而remove時，maintain需要注意判斷null，不然一旦亂搞，這棵樹就完了。而null時，一般都是o->ch[0]==null&&o->ch[1]==null，在d==-1時if(o->ch[0]==null) o=o->ch[1];這樣是很明顯的。

　　我們在進行區間操作時，一般都會把操作的區間split出來，防止其他元素糾結，之後在merge回去。此題無需關心insert，但是如果有insert，插入之後還應splay一下，隻有這樣才能擺脫鍊的詛咒。

　　第一次敲splay，真的很苦啊。

1 /**************************************************************
 2     Problem: 3223
 3     User: Doggu
 4     Language: C++
 5     Result: Accepted
 6     Time:2184 ms
 7     Memory:2776 kb
 8 ****************************************************************/
 9  
10 #include <cstdio>
11 #include <algorithm>
12 const int N = 100010;
13 struct Node {
14     int val, siz;
15     bool rev;
16     Node *ch[2];
17     int cmp(int k) {
18     if(k<=ch[0]->siz) return 0;
19     if(k<=ch[0]->siz+1) return -1;
20     return 1;
21     }
22     void pushdown() {if(rev) {
23     std::swap(ch[0],ch[1]);
24     ch[0]->rev^=1;
25     ch[1]->rev^=1;
26     rev = 0;    
27     }}
28     void maintain() {
29     siz=ch[0]->siz+ch[1]->siz+1;
30     }
31 }pool[N], *tail=pool, *null=pool, *root;
32 //int aa[N];
33 void rotate(Node *&o,int d) {
34     Node *k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
35     o->maintain();k->maintain();o=k;
36 }
37 Node *build(int lf,int rg) {
38     Node *o=++tail;
39     int mid=(lf+rg)>>1;
40     o->val=mid;//aa[mid];
41     o->ch[0]=(lf<=mid-1)?build(lf,mid-1):null;
42     o->ch[1]=(mid+1<=rg)?build(mid+1,rg):null;
43     o->maintain();
44     return o;
45 }
46 void splay(Node *&o,int k) {
47     o->pushdown();
48     int d=o->cmp(k);
49     if(d==1) k-=o->ch[0]->siz+1;
50     if(d!=-1) splay(o->ch[d],k), rotate(o,d^1);
51 }
52 Node *merge(Node *left,Node *right) {
53     if(left==null) return right;
54     splay(left,left->siz);
55     left->ch[1]=right;left->maintain();
56     return left;
57 }
58 void split(Node *o,int k,Node *&left,Node *&right) {
59     if(k==0) left=null, right=o;
60     else {
61     splay(o,k);
62     left=o;right=o->ch[1];
63     o->ch[1]=null;left->maintain();
64     }
65 }
66 void print(Node *o) {
67     if(o==null) return ;
68     o->pushdown();
69     print(o->ch[0]);
70     printf("%d ",o->val);
71     print(o->ch[1]);
72 }
73 int main() {
74     null->ch[0]=null->ch[1]=null;
75     int n, q, lf, rg;
76     scanf("%d%d",&n,&q);
77     //for( int i = 1; i <= n; i++ ) scanf("%d",&aa[i]);
78     root=build(1,n);
79     //printf("ROOT_SEQ:");print(root);printf("\n");
80     while(q--) {
81     scanf("%d%d",&lf,&rg);
82     Node *left, *mid, *right, *o;
83     split(root,rg,mid,right);
84     split(mid,lf-1,left,mid);
85     //printf("LEFT_SEQ:");print(left);printf("\n");
86     //printf("MID_SEQ:");print(mid);printf("\n");
87     //printf("RIGHT_SEQ:");print(right);printf("\n");
88     mid->rev^=1;
89     root=merge(merge(left,mid),right);
90     //printf("ROOT_SEQ:");print(root);printf("\n");
91     }
92     print(root);printf("\n");
93     return 0;
94 }
95

單旋

1 /**************************************************************
  2     Problem: 3223
  3     User: Doggu
  4     Language: C++
  5     Result: Accepted
  6     Time:2004 ms
  7     Memory:2776 kb
  8 ****************************************************************/
  9  
 10 #include <cstdio>
 11 #include <algorithm>
 12 const int N = 100010;
 13 struct Node {
 14     int val, siz;
 15     bool rev;
 16     Node *ch[2];
 17     int cmp(int k) {
 18     if(k<=ch[0]->siz) return 0;
 19     if(k<=ch[0]->siz+1) return -1;
 20     return 1;
 21     }
 22     void pushdown() {if(rev) {
 23     std::swap(ch[0],ch[1]);
 24     ch[0]->rev^=1;
 25     ch[1]->rev^=1;
 26     rev = 0;    
 27     }}
 28     void maintain() {
 29     siz=ch[0]->siz+ch[1]->siz+1;
 30     }
 31 }pool[N], *tail=pool, *null=pool, *root;
 32 //int aa[N];
 33 void rotate(Node *&o,int d) {
 34     Node *k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
 35     o->maintain();k->maintain();o=k;
 36 }
 37 Node *build(int lf,int rg) {
 38     Node *o=++tail;
 39     int mid=(lf+rg)>>1;
 40     o->val=mid;//aa[mid];
 41     o->ch[0]=(lf<=mid-1)?build(lf,mid-1):null;
 42     o->ch[1]=(mid+1<=rg)?build(mid+1,rg):null;
 43     o->maintain();
 44     return o;
 45 }
 46 void splay(Node *&o,int k) {
 47     o->pushdown();
 48     int d=o->cmp(k);
 49     if(d==1) k-=o->ch[0]->siz+1;
 50     if(d!=-1) {
 51     Node *p=o->ch[d];
 52     p->pushdown();
 53     int d2=p->cmp(k);
 54     int k2=(d2==0?k:k-p->ch[0]->siz-1);
 55     if(d2!=-1) {
 56         splay(p->ch[d2],k2);
 57         if(d==d2) rotate(o,d^1);else rotate(o->ch[d],d);
 58     }
 59     rotate(o,d^1);
 60     }
 61 }
 62 Node *merge(Node *left,Node *right) {
 63     if(left==null) return right;
 64     splay(left,left->siz);
 65     left->ch[1]=right;left->maintain();
 66     return left;
 67 }
 68 void split(Node *o,int k,Node *&left,Node *&right) {
 69     if(k==0) left=null, right=o;
 70     else {
 71     splay(o,k);
 72     left=o;right=o->ch[1];
 73     o->ch[1]=null;left->maintain();
 74     }
 75 }
 76 void print(Node *o) {
 77     if(o==null) return ;
 78     o->pushdown();
 79     print(o->ch[0]);
 80     printf("%d ",o->val);
 81     print(o->ch[1]);
 82 }
 83 int main() {
 84     null->ch[0]=null->ch[1]=null;
 85     int n, q, lf, rg;
 86     scanf("%d%d",&n,&q);
 87     //for( int i = 1; i <= n; i++ ) scanf("%d",&aa[i]);
 88     root=build(1,n);
 89     //printf("ROOT_SEQ:");print(root);printf("\n");
 90     while(q--) {
 91     scanf("%d%d",&lf,&rg);
 92     Node *left, *mid, *right, *o;
 93     split(root,rg,mid,right);
 94     split(mid,lf-1,left,mid);
 95     //printf("LEFT_SEQ:");print(left);printf("\n");
 96     //printf("MID_SEQ:");print(mid);printf("\n");
 97     //printf("RIGHT_SEQ:");print(right);printf("\n");
 98     mid->rev^=1;
 99     root=merge(merge(left,mid),right);
100     //printf("ROOT_SEQ:");print(root);printf("\n");
101     }
102     print(root);printf("\n");
103     return 0;
104 }
105

雙旋

轉載于:https://www.cnblogs.com/Doggu/p/bzoj3223.html

C/C++ 資料結構與算法
上一篇: bzoj 3223: Tyvj 1729 文藝平衡樹
下一篇: [BZOJ 3223]Tyvj 1729 文藝平衡樹

繼續閱讀