愉悦身心的splay
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #define rd read()
5 #define ll long long
6 using namespace std;
7
8 const int N = 1e5;
9 const ll inf = 1e18;
10
11 int ch[N][2], f[N], size[N], rt, add[N], tn[N], tot;
12 int n, q;
13 ll key[N], MAX[N];
14
15 int read() {
16 int X = 0, p = 1; char c = getchar();
17 for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p = -1;
18 for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0';
19 return X * p;
20 }
21
22 void update(int nd) {
23 int lson = ch[nd][0], rson = ch[nd][1];
24 size[nd] = size[ch[nd][0]] + size[ch[nd][1]] + 1;
25 MAX[nd] = key[nd];
26 if(lson) MAX[nd] = max(MAX[nd], MAX[ch[nd][0]]);
27 if(rson) MAX[nd] = max(MAX[nd], MAX[ch[nd][1]]);
28 }
29
30 void pushdown(int nd) {
31 int lson = ch[nd][0], rson = ch[nd][1];
32 if(tn[nd]) {
33 swap(ch[nd][0], ch[nd][1]);
34 if(ch[nd][0]) tn[ch[nd][0]] ^= 1;
35 if(ch[nd][1]) tn[ch[nd][1]] ^= 1;
36 tn[nd] = 0;
37 }
38 if(add[nd]) {
39 if(lson) key[lson] += add[nd], MAX[lson] += add[nd];
40 if(rson) key[rson] += add[nd], MAX[rson] += add[nd];
41 if(lson) add[lson] += add[nd];
42 if(rson) add[rson] += add[nd];
43 add[nd] = 0;
44 }
45 }
46
47 int get(int x) {
48 pushdown(f[x]);
49 return x == ch[f[x]][1];
50 }
51
52 void rotate(int x) {
53 int old = f[x], oldf = f[old], son = ch[x][get(x) ^ 1];
54 pushdown(old); pushdown(x);
55 if(oldf) ch[oldf][get(old)] = x;
56 ch[x][get(x) ^ 1] = old;
57 ch[old][get(x)] = son;
58 f[old] = x; f[x] = oldf; f[son] = old;
59 update(old); update(x);
60 }
61
62 void splay(int x, int d) {
63 for(int fa; (fa = f[x]) != d; rotate(x))
64 if(f[fa] != d ) rotate( get(fa) == get(x) ? fa : x);
65 if(!d) rt = x;
66 }
67
68 int build(int l, int r, int fa) {
69 if(l > r) return 0;
70 int mid = ( l + r ) >> 1, now = ++tot;
71 MAX[now] = key[now] = 0;
72 f[now] =fa;
73 ch[now][0] = build(l, mid - 1, now);
74 ch[now][1] = build(mid + 1, r, now);
75 update(now);
76 return now;
77 }
78
79 void init() {
80 rt = ++tot;
81 int rson = ++tot;
82 ch[rt][1] = rson;
83 f[rson] = rt;
84 ch[rson][0] = build(1, n, rson);
85 update(rson); update(rt);
86 }
87
88 int find_k(int k) {
89 int now = rt;
90 for(; ;) {
91 pushdown(now);
92 if(ch[now][0] && k <= size[ch[now][0]]) {now = ch[now][0]; continue;}
93 if(k == size[ch[now][0]] + 1) return now;
94 k -= size[ch[now][0]] + 1;
95 now = ch[now][1];
96 }
97 }
98
99 void cg_ad(int l, int r, int d) {
100 int pr = find_k(l - 1), nx = find_k(r + 1), lson;
101 splay(pr, 0); splay(nx, pr);
102 add[lson = ch[nx][0]] += d;
103 key[lson] += d;
104 MAX[lson] += d;
105 }
106
107 void turn(int l, int r) {
108 int pr = find_k(l - 1), nx = find_k(r + 1);
109 splay(pr, 0); splay(nx, pr);
110 tn[ch[nx][0]] ^= 1;
111 }
112
113 ll query(int l, int r) {
114 int pr = find_k(l - 1), nx = find_k(r + 1), lson;
115 splay(pr, 0); splay(nx, pr);
116 pushdown(lson = ch[nx][0]);
117 return MAX[lson];
118 }
119
120 int main()
121 {
122 n = rd; q = rd;
123 init();
124 for(; q; q--) {
125 int k = rd, x = rd + 1, y = rd + 1;
126 if(k == 1) cg_ad(x, y, rd);
127 if(k == 2) turn(x, y);
128 if(k == 3) printf("%lld\n", query(x, y));
129 }
130 } View Code
转载于:https://www.cnblogs.com/cychester/p/9517065.html