acdream 1738 世風日下的嘩啦啦族I，acdream1738
原題鏈接：http://acdream.info/problem?pid=1738
樹套樹裸題，如下：
![]()
1 #include<algorithm>
2 #include<iostream>
3 #include<cstdlib>
4 #include<cstring>
5 #include<cstdio>
6 #define lc root<<1
7 #define rc root<<1|1
8 using std::sort;
9 using std::lower_bound;
10 using std::upper_bound;
11 const int Max_N = 50010;
12 const int INF = ~0u >> 1;
13 struct Node {
14 int v, s, c;
15 Node *ch[2];
16 inline void set(int _v, int _s, Node *p) {
17 v = _v, s = c = _s;
18 ch[0] = ch[1] = p;
19 }
20 inline void push_up() {
21 s = ch[0]->s + ch[1]->s + c;
22 }
23 inline int cmp(int x) const {
24 return x == v ? -1 : x > v;
25 }
26 };
27 struct SizeBalanceTree {
28 int top, ans, tot, sum, arr[Max_N];
29 Node *null, *tail, stack[Max_N * 18];
30 Node *store[Max_N << 2], *ptr[Max_N << 2];
31 inline void init(int n) {
32 top = 0;
33 tail = &stack[0];
34 null = tail++;
35 null->set(0, 0, NULL);
36 for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
37 seg_built(1, 1, n);
38 }
39 inline Node *newNode(int v) {
40 Node *p = null;
41 if (!top) p = tail++;
42 else p = store[--top];
43 p->set(v, 1, null);
44 return p;
45 }
46 inline void rotate(Node *&x, int d) {
47 Node *k = x->ch[!d];
48 x->ch[!d] = k->ch[d];
49 k->ch[d] = x;
50 k->s = x->s;
51 x->push_up();
52 x = k;
53 }
54 inline void Maintain(Node *&x, int d) {
55 if (!x->ch[d]->s) return;
56 if (x->ch[d]->ch[d]->s > x->ch[!d]->s) {
57 rotate(x, !d);
58 } else if (x->ch[d]->ch[!d]->s > x->ch[!d]->s) {
59 rotate(x->ch[d], d), rotate(x, !d);
60 } else {
61 return;
62 }
63 Maintain(x, 0), Maintain(x, 1);
64 }
65 inline void insert(Node *&x, int v) {
66 if (x == null) {
67 x = newNode(v);
68 return;
69 } else {
70 x->s++;
71 int d = x->cmp(v);
72 if (-1 == d) {
73 x->c++;
74 return;
75 }
76 insert(x->ch[d], v);
77 x->push_up();
78 Maintain(x, d);
79 }
80 }
81 inline void del(Node *&x, int v) {
82 if (!x->s) return;
83 x->s--;
84 int d = x->cmp(v);
85 if (-1 == d) {
86 if (x->c > 1) {
87 x->c--;
88 return;
89 } else if (!x->ch[0]->s || !x->ch[1]->s) {
90 store[top++] = x;
91 x = x->ch[0]->s ? x->ch[0] : x->ch[1];
92 } else {
93 Node *ret = x->ch[1];
94 for (; ret->ch[0]->s; ret = ret->ch[0]);
95 del(x->ch[1], x->v = ret->v);
96 }
97 } else {
98 del(x->ch[d], v);
99 }
100 if (x->s) x->push_up();
101 }
102 inline Node *get_min(Node *x) {
103 for (; x->ch[0]->s; x = x->ch[0]);
104 return x;
105 }
106 inline int find(Node *x, int v) {
107 while (x->s && x->v != v) x = x->ch[v > x->v];
108 return x->c;
109 }
110 inline int count(Node *x, int v) {
111 int res = 0, t = 0;
112 for (; x->s;) {
113 t = x->ch[0]->s;
114 if (v < x->v) x = x->ch[0];
115 else res += t + x->c, x = x->ch[1];
116 }
117 return res;
118 }
119 inline void seg_built(int root, int l, int r) {
120 ptr[root] = null;
121 for (int i = l; i <= r; i++) insert(ptr[root], arr[i]);
122 if (l == r) return;
123 int mid = (l + r) >> 1;
124 seg_built(lc, l, mid);
125 seg_built(rc, mid + 1, r);
126 }
127 inline void seg_modify(int root, int l, int r, int pos, int v){
128 if (pos > r || pos < l) return;
129 del(ptr[root], arr[pos]);
130 insert(ptr[root], v);
131 if (l == r) return;
132 int mid = (l + r) >> 1;
133 seg_modify(lc, l, mid, pos, v);
134 seg_modify(rc, mid + 1, r, pos, v);
135 }
136 inline void seg_query_min(int root, int l, int r, int x, int y) {
137 if (x > r || y < l) return;
138 if (x <= l && y >= r) {
139 Node *ret = get_min(ptr[root]);
140 if (ret->v < ans) ans = ret->v;
141 return;
142 }
143 int mid = (l + r) >> 1;
144 seg_query_min(lc, l, mid, x, y);
145 seg_query_min(rc, mid + 1, r, x, y);
146 }
147 inline void seg_query_tot(int root, int l, int r, int x, int y, int val) {
148 if (x > r || y < l) return;
149 if (x <= l && y >= r) {
150 tot += find(ptr[root], val);
151 return;
152 }
153 int mid = (l + r) >> 1;
154 seg_query_tot(lc, l, mid, x, y, val);
155 seg_query_tot(rc, mid + 1, r, x, y, val);
156 }
157 inline void seg_query_count(int root, int l, int r, int x, int y, int val) {
158 if (x > r || y < l) return;
159 if (x <= l && y >= r) {
160 sum += count(ptr[root], val);
161 return;
162 }
163 int mid = (l + r) >> 1;
164 seg_query_count(lc, l, mid, x, y, val);
165 seg_query_count(rc, mid + 1, r, x, y, val);
166 }
167 inline void gogo(int n) {
168 int a, b, c, d;
169 scanf("%d", &a);
170 if (1 == a) {
171 scanf("%d %d", &b, &c);
172 seg_modify(1, 1, n, b, c), arr[b] = c;
173 } else if (2 == a) {
174 ans = INF, tot = 0;
175 scanf("%d %d", &b, &c);
176 seg_query_min(1, 1, n, b, c);
177 seg_query_tot(1, 1, n, b, c, ans);
178 printf("%d %d\n", ans, tot);
179 } else {
180 sum = 0;
181 scanf("%d %d %d", &b, &c, &d);
182 seg_query_count(1, 1, n, b, c, d);
183 printf("%d\n", sum);
184 }
185 }
186 }sbt;
187 int main() {
188 #ifdef LOCAL
189 freopen("in.txt", "r", stdin);
190 freopen("out.txt", "w+", stdout);
191 #endif;
192 int n, m;
193 while (~scanf("%d %d", &n, &m)) {
194 sbt.init(n);
195 while (m--) sbt.gogo(n);
196 }
197 return 0;
198 }
View Code
如果覺得sb樹跑的慢，再寫個紅黑樹吧。。。
![]()
1 #include<algorithm>
2 #include<iostream>
3 #include<cstdlib>
4 #include<cstring>
5 #include<cstdio>
6 #define lc root<<1
7 #define rc root<<1|1
8 const int Max_N = 50010;
9 const int INF = ~0u >> 1;
10 struct Node {
11 int data, s, c;
12 bool color;
13 Node *fa, *ch[2];
14 inline void set(int _v, bool _color, int i, Node *p) {
15 data = _v, color = _color, s = c = i;
16 fa = ch[0] = ch[1] = p;
17 }
18 inline void push_up() {
19 s = ch[0]->s + ch[1]->s + c;
20 }
21 inline void push_down() {
22 for (Node *x = this; x->s; x = x->fa) x->s--;
23 }
24 inline int cmp(int v) const {
25 return data == v ? -1 : v > data;
26 }
27 };
28 struct RedBlackTree {
29 int top, ans, tot, sum, arr[Max_N];
30 Node *null, *tail;
31 Node stack[Max_N * 18], *store[Max_N << 2], *ptr[Max_N << 2];
32 inline void init(int n) {
33 top = 0;
34 tail = &stack[0];
35 null = tail++;
36 null->set(0, 0, 0, NULL);
37 for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
38 seg_built(1, 1, n);
39 }
40 inline Node *newNode(int v) {
41 Node *p = null;
42 if (!top) p = tail++;
43 else p = store[--top];
44 p->set(v, 1, 1, null);
45 return p;
46 }
47 inline void rotate(int root, Node* &x, bool d) {
48 Node *y = x->ch[!d];
49 x->ch[!d] = y->ch[d];
50 if (y->ch[d]->s) y->ch[d]->fa = x;
51 y->fa = x->fa;
52 if (!x->fa->s) ptr[root] = y;
53 else x->fa->ch[x->fa->ch[0] != x] = y;
54 y->ch[d] = x;
55 x->fa = y;
56 y->s = x->s;
57 x->push_up();
58 }
59 inline void insert(int root, int v) {
60 Node *x = ptr[root], *y = null;
61 while (x->s) {
62 x->s++, y = x;
63 int d = x->cmp(v);
64 if (-1 == d) {
65 x->c++;
66 return;
67 }
68 x = x->ch[d];
69 }
70 x = newNode(v);
71 if (y->s) y->ch[v > y->data] = x;
72 else ptr[root] = x;
73 x->fa = y;
74 insert_fix(root, x);
75 }
76 inline void insert_fix(int root, Node* &x) {
77 while (x->fa->color) {
78 Node *par = x->fa, *Gp = par->fa;
79 bool d = par == Gp->ch[0];
80 Node *uncle = Gp->ch[d];
81 if (uncle->color) {
82 par->color = uncle->color = 0;
83 Gp->color = 1;
84 x = Gp;
85 } else if (x == par->ch[d]) {
86 rotate(root, x = par, !d);
87 } else {
88 Gp->color = 1;
89 par->color = 0;
90 rotate(root, Gp, d);
91 }
92 }
93 ptr[root]->color = 0;
94 }
95 inline Node *find(Node *x, int data) {
96 while (x->s && x->data != data) x = x->ch[x->data < data];
97 return x;
98 }
99 inline void del_fix(int root, Node* &x) {
100 while (x != ptr[root] && !x->color) {
101 bool d = x == x->fa->ch[0];
102 Node *par = x->fa, *sibling = par->ch[d];
103 if (sibling->color) {
104 sibling->color = 0;
105 par->color = 1;
106 rotate(root, x->fa, !d);
107 sibling = par->ch[d];
108 } else if (!sibling->ch[0]->color && !sibling->ch[1]->color) {
109 sibling->color = 1, x = par;
110 } else {
111 if (!sibling->ch[d]->color) {
112 sibling->ch[!d]->color = 0;
113 sibling->color = 1;
114 rotate(root, sibling, d);
115 sibling = par->ch[d];
116 }
117 sibling->color = par->color;
118 sibling->ch[d]->color = par->color = 0;
119 rotate(root, par, !d);
120 break;
121 }
122 }
123 x->color = 0;
124 }
125 inline void del(int root, int data) {
126 Node *z = find(ptr[root], data);
127 if (!z->s) return;
128 if (z->c > 1) {
129 z->c--;
130 z->push_down();
131 return;
132 }
133 Node *y = z, *x = null;
134 if (z->ch[0]->s && z->ch[1]->s) {
135 y = z->ch[1];
136 while (y->ch[0]->s) y = y->ch[0];
137 }
138 x = y->ch[!y->ch[0]->s];
139 x->fa = y->fa;
140 if (!y->fa->s) ptr[root] = x;
141 else y->fa->ch[y->fa->ch[1] == y] = x;
142 if (z != y) z->data = y->data, z->c = y->c;
143 y->fa->push_down();
144 for (Node *k = y->fa; y->c > 1 && k->s && k != z; k = k->fa) k->s -= y->c - 1;
145 if (!y->color) del_fix(root, x);
146 store[top++] = y;
147 }
148 inline Node* get_min(Node *x) {
149 for (; x->ch[0]->s; x = x->ch[0]);
150 return x;
151 }
152 inline int count(Node *x, int v) {
153 int res = 0, t = 0;
154 for (; x->s;) {
155 t = x->ch[0]->s;
156 if (v < x->data) x = x->ch[0];
157 else res += t + x->c, x = x->ch[1];
158 }
159 return res;
160 }
161 inline void seg_built(int root, int l, int r) {
162 ptr[root] = null;
163 for (int i = l; i <= r; i++) insert(root, arr[i]);
164 if (l == r) return;
165 int mid = (l + r) >> 1;
166 seg_built(lc, l, mid);
167 seg_built(rc, mid + 1, r);
168 }
169 inline void seg_modify(int root, int l, int r, int pos, int v){
170 if (pos > r || pos < l) return;
171 del(root, arr[pos]);
172 insert(root, v);
173 if (l == r) return;
174 int mid = (l + r) >> 1;
175 seg_modify(lc, l, mid, pos, v);
176 seg_modify(rc, mid + 1, r, pos, v);
177 }
178 inline void seg_query_min(int root, int l, int r, int x, int y) {
179 if (x > r || y < l) return;
180 if (x <= l && y >= r) {
181 Node *ret = get_min(ptr[root]);
182 if (ret->data < ans) ans = ret->data;
183 return;
184 }
185 int mid = (l + r) >> 1;
186 seg_query_min(lc, l, mid, x, y);
187 seg_query_min(rc, mid + 1, r, x, y);
188 }
189 inline void seg_query_tot(int root, int l, int r, int x, int y, int val) {
190 if (x > r || y < l) return;
191 if (x <= l && y >= r) {
192 tot += find(ptr[root], val)->c;
193 return;
194 }
195 int mid = (l + r) >> 1;
196 seg_query_tot(lc, l, mid, x, y, val);
197 seg_query_tot(rc, mid + 1, r, x, y, val);
198 }
199 inline void seg_query_count(int root, int l, int r, int x, int y, int val) {
200 if (x > r || y < l) return;
201 if (x <= l && y >= r) {
202 sum += count(ptr[root], val);
203 return;
204 }
205 int mid = (l + r) >> 1;
206 seg_query_count(lc, l, mid, x, y, val);
207 seg_query_count(rc, mid + 1, r, x, y, val);
208 }
209 inline void gogo(int n) {
210 int a, b, c, d;
211 scanf("%d", &a);
212 if (1 == a) {
213 scanf("%d %d", &b, &c);
214 seg_modify(1, 1, n, b, c), arr[b] = c;
215 } else if (2 == a) {
216 ans = INF, tot = 0;
217 scanf("%d %d", &b, &c);
218 seg_query_min(1, 1, n, b, c);
219 seg_query_tot(1, 1, n, b, c, ans);
220 printf("%d %d\n", ans, tot);
221 } else {
222 sum = 0;
223 scanf("%d %d %d", &b, &c, &d);
224 seg_query_count(1, 1, n, b, c, d);
225 printf("%d\n", sum);
226 }
227 }
228 }rbt;
229 int main() {
230 #ifdef LOCAL
231 freopen("in.txt", "r", stdin);
232 freopen("out.txt", "w+", stdout);
233 #endif
234 int n, m;
235 while (~scanf("%d %d", &n, &m)) {
236 rbt.init(n);
237 while (m--) rbt.gogo(n);
238 }
239 return 0;
240 }
View Code
