uva 11922 splay维护数列

splay第一题，有了Treap的基础以后感觉splay还是比较好理解的，splay的优势在于编程复杂度比较低且效率不错，通过splay操作以及衍生的split和merge操作可以实现很强大的功能。
  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 using namespace std;
  5 
  6 struct Node 
  7 {
  8     Node * ch[2];
  9     int val;
 10     int rank;
 11     int sz;
 12     int flip;
 13 
 14     int cmp( int x ) const 
 15     {
 16         if ( x == rank ) return -1;
 17         return x < rank ? 0 : 1;
 18     }
 19 
 20     void maintain()
 21     {
 22         sz = rank = 1;
 23         if ( ch[0] != NULL )
 24         {
 25             sz += ch[0]->sz;
 26             rank += ch[0]->sz;
 27         }
 28         if ( ch[1] != NULL )
 29         {
 30             sz += ch[1]->sz;
 31         }
 32     }
 33 
 34     void pushdown()
 35     {
 36         if ( flip )
 37         {
 38             swap( ch[0], ch[1] );
 39             flip = 0;
 40             if ( ch[0] != NULL ) ch[0]->flip ^= 1;
 41             if ( ch[1] != NULL ) ch[1]->flip ^= 1;
 42         }
 43     }
 44 };
 45 
 46 bool ok( int val )
 47 {
 48     return val != 0;
 49 }
 50 
 51 void inorder( Node * o )
 52 {
 53     if ( o == NULL ) return ;
 54     o->pushdown();
 55     inorder( o->ch[0] );
 56     if ( ok( o->val ) ) printf("%d
", o->val);
 57     inorder( o->ch[1] );
 58 }
 59 
 60 void rotate( Node * & o, int d )
 61 {
 62     Node * k = o->ch[d ^ 1];
 63     o->ch[d ^ 1] = k->ch[d];
 64     k->ch[d] = o;
 65     o->maintain();
 66     k->maintain();
 67     o = k;
 68 }
 69 
 70 void splay( Node * & o, int k )
 71 {
 72     o->pushdown();
 73     o->maintain();
 74     int d = o->cmp(k);
 75     if ( d != -1 )
 76     {
 77         if ( d == 1 ) k -= o->rank;
 78         Node * p = o->ch[d];
 79         p->pushdown();
 80         p->maintain();
 81         int d2 = p->cmp(k);
 82         if ( d2 != -1 )
 83         {
 84             int k2 = ( d2 == 0 ? k : k - p->rank );    
 85             splay( p->ch[d2], k2 );
 86             if ( d == d2 )
 87             {
 88                 rotate( o, d ^ 1 );
 89             }
 90             else
 91             {
 92                 rotate( o->ch[d], d );
 93             }
 94         }
 95         rotate( o, d ^ 1 );
 96     }
 97 }
 98 
 99 Node * build( int l, int r )
100 {
101     if ( l > r ) return NULL;
102     Node * o = new Node();
103     int mid = ( l + r ) >> 1;
104     o->sz = r - l + 1;
105     o->val = mid;
106     o->rank = mid - l + 1;
107     o->flip = 0;
108     o->ch[0] = build( l, mid - 1 );
109     o->ch[1] = build( mid + 1, r );
110     return o;
111 }
112 
113 void split( Node * o, int k, Node * & left, Node * & right )
114 {
115     splay( o, k );
116     left = o;
117     right = o->ch[1];
118     o->ch[1] = NULL;
119     left->maintain();
120 }
121 
122 Node * merge( Node * left, Node * right )
123 {
124     splay( left, left->sz );
125     left->ch[1] = right;
126     left->maintain();
127     return left;
128 }
129 
130 int main ()
131 {
132     int n, m;
133     while ( scanf("%d%d", &n, &m) != EOF )
134     {
135         Node * root = build( 0, n );
136         while ( m-- )
137         {
138             int a, b;
139             scanf("%d%d", &a, &b);
140             Node * left, * mid, * right, * o;
141                split( root, a, left, o );
142             split( o, b - a + 1, mid, right );
143             mid->flip ^= 1;
144             root = merge( merge( left, right ), mid );
145         }
146         inorder(root);
147     }
148     return 0;
149 }