題目傳送門：https://codeforces.com/problemset/problem/527/C
題意：給出一個面積為h×w的長方形，有m次操作，每次操作可以橫著或豎著在某個位置砍一刀，問你在m次操作后，在所有塊中面積最大的一個，
思路：理解題意，就是讓你求砍m次后，剩下的部分的最長的高和最長的寬，相乘就是最大面積，所以我們可以利用平衡樹中的前驅和后繼來求所切割點所在部分的長度，同時利用兩顆平衡樹來維護高和寬，再利用multiset來維護切割后的高度和寬度，每次切割時，要先在multiset中找到所要切割線段的長度，將其切割后再放回去，最后從multiset中找到最長的高和寬相乘即是所求答案，
代碼：
1 #include<cstdio>
2 #include<cstring>
3 #include<cstdlib>
4 #include<iostream>
5 #include<set>
6 #define int long long
7 using namespace std;
8 const int MAXN = 200005;
9 const int MOD = 2147483647;
10
11
12 multiset<int>mts;
13 multiset<int>mts_t;
14
15 struct Node
16 {
17 int left; //左子樹
18 int right; //右子樹
19 int size; //大小
20 int val; //值
21 int key; //平衡種子
22 }tree[MAXN], tree_t[MAXN];
23
24 int root, tot;
25
26 int add(int val) {
27 tot++;
28 tree[tot].size = 1;
29 tree[tot].val = val;
30 tree[tot].key = rand() % MOD;
31 tree[tot].left = 0;
32 tree[tot].right = 0;
33
34 return tot;
35 }
36
37 void update_root(int now) {
38 int left, right;
39
40 left = tree[now].left;
41 right = tree[now].right;
42
43 tree[now].size = tree[left].size + tree[right].size + 1;
44 }
45
46 //拆分(now原treap,a左子樹,b右子樹,val值)
47 void split_new(int now, int& a, int& b, int val) {
48 if (now == 0) {
49 a = 0;
50 b = 0;
51 return;
52 }
53
54 if (tree[now].val <= val) {//now左子樹中的所有值都小于now，
55 a = now;
56 split_new(tree[now].right, tree[a].right, b, val);
57 }
58 else {
59 b = now;
60 split_new(tree[now].left, a, tree[b].left, val);
61 }
62
63 update_root(now);
64 }
65
66 void merge_new(int& now, int a, int b) {
67 if (a == 0 || b == 0) {
68 now = a + b;
69 return;
70 }
71
72 //按照key值合并(堆性質)
73 if (tree[a].key < tree[b].key) {
74 /**
75 * a樹key值小于b樹，那么b樹屬于a樹的后代，因為b樹恒大于a樹，那么b樹一定屬于a樹的右后代，
76 * a的左子樹不變，直接賦給now，遞回合并a的右子樹和b
77 */
78 now = a;
79 merge_new(tree[now].right, tree[a].right, b);
80 }
81 else {
82 now = b;
83 merge_new(tree[now].left, a, tree[b].left);
84 }
85
86 update_root(now);
87 }
88
89 int find_new(int now, int rank) {//找第k大
90 while (tree[tree[now].left].size + 1 != rank) {
91 if (tree[tree[now].left].size >= rank) {
92 now = tree[now].left;
93 }
94 else {
95 rank -= tree[tree[now].left].size + 1;
96 now = tree[now].right;
97 }
98 }
99 return tree[now].val;
100 //cout << tree[now].val << "\n";
101 }
102
103 void insert_new(int val) {
104 int x, y, z;
105
106 x = 0;
107 y = 0;
108 z = add(val);
109 split_new(root, x, y, val);
110 merge_new(x, x, z);
111 merge_new(root, x, y);
112 }
113
114 void del_new(int val) {
115 int x, y, z;
116
117 x = y = z = 0;
118 split_new(root, x, y, val);
119 split_new(x, x, z, val - 1);
120 merge_new(z, tree[z].left, tree[z].right);
121 merge_new(x, x, z);
122 merge_new(root, x, y);
123 }
124
125 void get_rank(int val) {
126 int x, y;
127
128 x = y = 0;
129 split_new(root, x, y, val - 1);
130 cout << tree[x].size + 1 << "\n";
131 merge_new(root, x, y);
132 }
133
134 void get_val(int rank) {
135 cout << find_new(root, rank) << "\n";
136 }
137
138 int l, r;
139 void get_pre(int val) {
140 int x, y;
141
142 x = y = 0;
143 split_new(root, x, y, val - 1);
144 l = find_new(x, tree[x].size);
145 merge_new(root, x, y);
146 }
147
148 void get_next(int val) {
149 int x, y;
150
151 x = y = 0;
152 split_new(root, x, y, val);
153 r = find_new(y, 1);
154 merge_new(root, x, y);
155 }
156
157 int root_t, tot_t;
158
159 int add_t(int val) {
160 tot_t++;
161 tree_t[tot_t].size = 1;
162 tree_t[tot_t].val = val;
163 tree_t[tot_t].key = rand() % MOD;
164 tree_t[tot_t].left = 0;
165 tree_t[tot_t].right = 0;
166
167 return tot_t;
168 }
169
170 void update_root_t(int now) {
171 int left, right;
172
173 left = tree_t[now].left;
174 right = tree_t[now].right;
175
176 tree_t[now].size = tree_t[left].size + tree_t[right].size + 1;
177 }
178
179 //拆分(now原treap,a左子樹,b右子樹,val值)
180 void split_new_t(int now, int& a, int& b, int val) {
181 if (now == 0) {
182 a = 0;
183 b = 0;
184 return;
185 }
186
187 if (tree_t[now].val <= val) {//now左子樹中的所有值都小于now，
188 a = now;
189 split_new_t(tree_t[now].right, tree_t[a].right, b, val);
190 }
191 else {
192 b = now;
193 split_new_t(tree_t[now].left, a, tree_t[b].left, val);
194 }
195
196 update_root_t(now);
197 }
198
199 void merge_new_t(int& now, int a, int b) {
200 if (a == 0 || b == 0) {
201 now = a + b;
202 return;
203 }
204
205 //按照key值合并(堆性質)
206 if (tree_t[a].key < tree_t[b].key) {
207 /**
208 * a樹key值小于b樹，那么b樹屬于a樹的后代，因為b樹恒大于a樹，那么b樹一定屬于a樹的右后代，
209 * a的左子樹不變，直接賦給now，遞回合并a的右子樹和b
210 */
211 now = a;
212 merge_new_t(tree_t[now].right, tree_t[a].right, b);
213 }
214 else {
215 now = b;
216 merge_new_t(tree_t[now].left, a, tree_t[b].left);
217 }
218
219 update_root_t(now);
220 }
221
222 int find_new_t(int now, int rank) {//找第k大
223 while (tree_t[tree_t[now].left].size + 1 != rank) {
224 if (tree_t[tree_t[now].left].size >= rank) {
225 now = tree_t[now].left;
226 }
227 else {
228 rank -= tree_t[tree_t[now].left].size + 1;
229 now = tree_t[now].right;
230 }
231 }
232 return tree_t[now].val;
233 }
234
235 void insert_new_t(int val) {
236 int x, y, z;
237
238 x = 0;
239 y = 0;
240 z = add_t(val);
241 split_new_t(root_t, x, y, val);
242 merge_new_t(x, x, z);
243 merge_new_t(root_t, x, y);
244 }
245
246 void del_new_t(int val) {
247 int x, y, z;
248
249 x = y = z = 0;
250 split_new_t(root_t, x, y, val);
251 split_new_t(x, x, z, val - 1);
252 merge_new_t(z, tree_t[z].left, tree_t[z].right);
253 merge_new_t(x, x, z);
254 merge_new_t(root_t, x, y);
255 }
256
257 void get_rank_t(int val) {
258 int x, y;
259
260 x = y = 0;
261 split_new_t(root_t, x, y, val - 1);
262 cout << tree_t[x].size + 1 << "\n";
263 merge_new_t(root_t, x, y);
264 }
265
266 void get_val_t(int rank) {
267 find_new_t(root_t, rank);
268 }
269
270 int lt, rt;
271 void get_pre_t(int val) {
272 int x, y;
273
274 x = y = 0;
275 split_new_t(root_t, x, y, val - 1);
276 lt = find_new_t(x, tree_t[x].size);
277 merge_new_t(root_t, x, y);
278 }
279
280 void get_next_t(int val) {
281 int x, y;
282
283 x = y = 0;
284 split_new_t(root_t, x, y, val);
285 rt = find_new_t(y, 1);
286 merge_new_t(root_t, x, y);
287 }
288
289
290
291 signed main() {
292
293 ios::sync_with_stdio(false);
294 cin.tie(0);
295
296 int w, h, n;
297 cin >> w >> h >> n;
298
299 memset(tree, 0, sizeof(tree));
300
301 add(MOD);
302 root = 1;
303 tree[root].size = 0;
304 add_t(MOD);
305 root_t = 1;
306 tree_t[root_t].size = 0;
307
308 insert_new(0);
309 insert_new(h);
310 mts.insert(h - 0);
311 /*get_val(1);
312 get_val(2);*/
313 insert_new_t(0);
314 insert_new_t(w);
315 mts_t.insert(w - 0);
316 multiset<int>::iterator it;
317 for (int i = 0; i < n; i++) {
318 char ch;
319 int x;
320 cin >> ch >> x;
321 if (ch == 'H') {
322 insert_new(x);
323 /*get_val(1);
324 get_val(2);
325 get_val(3);*/
326 get_pre(x);
327 get_next(x);
328 int hh = r - l;
329
330 it = mts.find(hh);
331 mts.erase(it);
332
333 mts.insert(x - l);
334 mts.insert(r - x);
335 }
336 else {
337 insert_new_t(x);
338 get_pre_t(x);
339 get_next_t(x);
340 int ww = rt - lt;
341
342 it = mts_t.find(ww);
343 mts_t.erase(it);
344
345 mts_t.insert(x - lt);
346 mts_t.insert(rt - x);
347 }
348 multiset<int>::reverse_iterator rit = mts.rbegin();
349 int maxh = *(rit);
350 multiset<int>::reverse_iterator rit_t = mts_t.rbegin();
351 int maxw = *(rit_t);
352 int ans = maxh * maxw;
353 cout << ans << "\n";
354 }
355
356 return 0;
357 }
永遠熱愛，永遠向著光，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/500194.html
標籤：其他