BZOJ3223 Tyvj1729 文艺平衡树

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #define rep(i,l,r) for(int i=l; i<=r; i++)
 6 #define clr(x,y) memset(x,y,sizeof(x))
 7 #define travel(x) for(Edge *p=last[x]; p; p=p->pre)
 8 using namespace std;
 9 const int INF = 0x3f3f3f3f;
10 const int maxn = 100010;
11 inline int read(){
12     int ans = 0, f = 1;
13     char c = getchar();
14     for(; !isdigit(c); c = getchar())
15     if (c == '-') f = -1;
16     for(; isdigit(c); c = getchar())
17     ans = ans * 10 + c - '0';
18     return ans * f;
19 }
20 struct Node{
21     Node *ch[2];
22     int v,s;
23     bool rev;
24     Node() : s(0){}
25     inline int cmp(int x) const{
26         x -= ch[0]->s;
27         if (x == 1) return -1;
28         return x <= 0 ? 0 : 1;
29     }
30     inline void pushdown(){
31         if (!rev) return;
32         rev = 0; swap(ch[0],ch[1]);
33         ch[0]->rev ^= 1; ch[1]->rev ^= 1;
34     }
35     inline void maintain(){
36         s = ch[0]->s + ch[1]->s + 1;
37     }
38 }t[maxn];
39 Node *pt = t, *null = pt++, *root;
40 int n,m,l,r;
41 inline Node *newnode(int x){
42     pt->v = x; pt->s = 1; pt->rev = 0; pt->ch[0] = pt->ch[1] = null;
43     return pt++;
44 }
45 inline void rotate(Node *&o,int d){
46     Node *k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o;
47     o->maintain(); k->maintain(); o = k; 
48 }
49 Node *build(int u,int v){
50     if (u >= v) return null;
51     int mid = (u + v) >> 1;
52     Node *ret = newnode(mid);
53     if (u < mid) ret->ch[0] = build(u,mid);
54     if (mid+1 < v) ret->ch[1] = build(mid+1,v);
55     ret->maintain();
56     return ret;
57 }
58 void splay(Node *&o,int k){
59     o->pushdown();
60     int d = o->cmp(k);
61     if (d == 1) k -= o->ch[0]->s + 1;
62     if (d != -1){
63         Node *p = o->ch[d]; p->pushdown();
64         int d2 = p->cmp(k);
65         int k2 = d2 ? k - p->ch[0]->s - 1 : k;
66         if (d2 != -1){
67             splay(p->ch[d2],k2);
68             d == d2 ? rotate(o,d^1) : rotate(o->ch[d],d);
69         }
70         rotate(o,d^1);
71     }
72 }
73 inline void reverse(int l,int r){
74     splay(root,l); splay(root->ch[1],r - root->ch[0]->s + 1);
75     root->ch[1]->ch[0]->rev ^= 1;
76 }
77 void dfs(Node *o){
78     if (o == null) return;
79     o->pushdown();
80     dfs(o->ch[0]);
81     if (o->v >= 1 && o->v <= n) printf("%d ",o->v);
82     dfs(o->ch[1]);
83 }
84 int main(){
85     n = read(); m = read();
86     root = build(0,n+2);
87     rep(i,1,m){
88         l = read(); r = read();
89         if (l == r) continue;
90         reverse(l,r);
91     }
92     dfs(root);
93     return 0;
94 }