「BZOJ 3337」ORZJRY I-块状链表

题意很清晰,直接给链接。

链接

BZOJ 3337

题解

先 %nzhtl1477 大爷的 ODT,太强辣!!!

然而并不会 ODT,还是写块链吧,听说 BZOJ 有 O2,那我们就大胆的用 list 套 vector 写块链吧

首先操作 1, 2 是基础操作,就不多说了。
先看操作 5, 6, 7,我们维护 $\text{delta}, \text{cover}, \text{sum}$ 标记,表示增加值和覆盖值及元素和,对于连续的块打标记,对于零散的元素暴力修改即可,暴力修改的时候不要忘记更新 $\text{sum}$,值得注意的是后出现的覆盖值是可以清除 $\text{delta}$ 标记的。

然后操作 3,我们维护一个 $\text{rev}$ 标记,下传的时候反转,注意标记不要过于频繁地下传,用到的时候在下传,否则可能会 TLE。我们先将区间 $[l, r]$ 从块链中拆分出来,即 split(l - 1), split(r),然后对于区间 $[l, r]$ 中的每一块都打上反转标记,但我们发现只打标记还不够,区间中的整块也要翻转,这里就用到了 std::list::splice 方法了。

  • void splice( const_iterator pos, list& other ),把 $\text{other}$ 接在 $\text{pos}$ 前面,并清空 $\text{other}$,时间消耗为常数。
  • void splice( const_iterator pos, list& other, const_iterator first, const_iterator last),把 $\text{other}$ 中的 $[first, last)$ 接在 $\text{pos}$ 前面并清空对应区间,时间消耗对应区间长度。

所以我们可以先开一个临时的 list,然后将 $[l, r]$ splice 进去,调用 std::list::reverse 即完成了翻转,然后再用第一种 splice 接回去。

对于操作 5,我们同样使用 splice(list 的 splice 真好用),先提取区间 $[l, r]$,然后 splice 出 $(r - k, r]$,再 splice 接回去。

对于操作 8, 9,由于还要查 rank,我们显然还维护了一个排序后的数组,有了这个数组,这两个操作就很容易了,注意一下 $\text{delta}$ 和 $\text{cover}$ 标记的处理就可以了。

对于操作 11,先暴力统计零散元素中 $< \text{val}$ 的个数,然后对于整块的元素,先判断是否存在 $\text{cover}$ 标记,看其是否会产生整块的贡献,同时也避免了标记下传的巨大常数,若不存在 $\text{cover}$ 标记,我们在考虑 $\text{delta}$ 标记,由于是整块增加了 $\text{delta}$,我们完全可以看做是 $\text{val} - \text{delta}$,而块内元素不变,所以我们在这块所维护的排序数组中二分就可以快速统计出当前块 $< \text{val} - \text{delta}$ 的个数,累加即可。

对于操作 10,二分第 $k$ 小的元素,我们先求出所有元素最大值作为上界,然后统计 $\leq \text{mid}$ 元素的个数,判断是否 $\geq k$,对于统计,同操作 11,我们还是先判断是否有 $\text{cover}$,然后二分 $mid - delta$

最终的结果也证明了 STL 写法的块状链表确实不慢,虽然快不过 ODT,但目前应该是块链中最快的,想一想 vector 暴力能过普通平衡树,所以 std::liststd::vector 可能也是一种优越的实现方法。

代码

我真的不是把每个操作都复制了一遍(雾)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
/**
* Copyright (c) 2017, xehoth
* All rights reserved.
* 「BZOJ 3337」ORZJRY I 30-09-2017
* 块状链表
* @author xehoth
*/
#include <bits/stdc++.h>
namespace IO {
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
return s == t ? -1 : *s++;
}
template <typename T>
inline void read(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return;
c == '-' ? iosig = true : 0;
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
iosig ? x = -x : 0;
}
inline void read(char &c) {
while (c = read(), isspace(c) && c != -1)
;
}
inline int read(char *buf) {
register int s = 0;
register char c;
while (c = read(), isspace(c) && c != -1)
;
if (c == -1) {
*buf = 0;
return -1;
}
do
buf[s++] = c;
while (c = read(), !isspace(c) && c != -1);
buf[s] = 0;
return s;
}
const int OUT_LEN = 1000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
*oh++ = c;
}
template <typename T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
} else {
x < 0 ? (print('-'), x = -x) : 0;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
struct InputOutputStream {
template <typename T>
inline InputOutputStream &operator>>(T &x) {
read(x);
return *this;
}
template <typename T>
inline InputOutputStream &operator<<(const T &x) {
print(x);
return *this;
}
~InputOutputStream() { flush(); }
} io;
} // end IO
namespace {
#define long long long
const int MAXN = 100000;
int blockCount;
int blockSize;
typedef std::vector<int> Vector;
struct Block {
Vector num, sorted;
int delta, cover;
bool rev;
long sum;
Block() : delta(0), cover(0), rev(false), sum(0) {}
inline void pushDown() {
if (rev) std::reverse(num.begin(), num.end()), rev = false;
if (delta) {
for (register int i = 0; i < num.size(); i++)
num[i] += delta, sorted[i] += delta;
sum += (long)delta * num.size();
delta = 0;
}
if (cover) {
for (register int i = 0; i < num.size(); i++)
num[i] = sorted[i] = cover;
sum = (long)cover * num.size();
cover = 0;
}
}
inline long getSum() {
return cover ? (long)cover * num.size()
: sum + (long)delta * num.size();
}
inline long getMax() { return cover ? cover : sorted.back() + (long)delta; }
inline long getMin() { return cover ? cover : sorted[0] + (long)delta; }
};
typedef std::list<Block> List;
typedef List::iterator Iterator;
List d;
inline void build(const int *a, const int n) {
blockSize = std::max((sqrt(n) + 1) * 4 / 3, 1.0);
blockCount = ceil((double)n / blockSize);
d.resize(blockCount);
register Iterator it = d.begin();
for (register int i = 0, j = 0; i < blockCount; i++, it++) {
j += blockSize;
it->num.assign(a + j - blockSize, a + std::min(j, n));
it->sorted.assign(a + j - blockSize, a + std::min(j, n));
for (Vector::iterator v = it->num.begin(); v != it->num.end(); v++)
it->sum += *v;
std::sort(it->sorted.begin(), it->sorted.end());
}
}
using IO::io;
inline void find(int cur, Iterator &it, int &pos) {
for (it = d.begin(); (int)(cur - it->num.size()) >= 0 && it != d.end();)
cur -= it->num.size(), it++;
pos = cur;
it->pushDown();
}
inline void split(Iterator cur, int pos) {
if (pos == cur->num.size()) return;
Iterator it = cur;
it = d.insert(++it, Block());
cur->pushDown();
it->num.assign(cur->num.begin() + pos, cur->num.end());
cur->num.erase(cur->num.begin() + pos, cur->num.end());
cur->sorted.erase(cur->sorted.begin() + pos, cur->sorted.end());
it->sorted.assign(it->num.begin(), it->num.end());
for (Vector::iterator v = it->num.begin(); v != it->num.end(); v++)
it->sum += *v;
cur->sum -= it->sum;
cur->sorted.assign(cur->num.begin(), cur->num.end());
std::sort(it->sorted.begin(), it->sorted.end());
std::sort(cur->sorted.begin(), cur->sorted.end());
}
inline void merge(Iterator cur, Iterator suc) {
cur->pushDown();
suc->pushDown();
cur->num.insert(cur->num.end(), suc->num.begin(), suc->num.end());
cur->sorted.insert(cur->sorted.end(), suc->sorted.begin(),
suc->sorted.end());
cur->sum += suc->sum;
std::sort(cur->sorted.begin(), cur->sorted.end());
d.erase(suc);
}
inline void maintain(Iterator cur) {
for (register Iterator tmp; cur != d.end(); cur++) {
if (cur->num.size() > blockSize * 2) {
split(cur, cur->num.size() / 2);
} else if (cur->num.size() < blockSize / 2) {
tmp = cur, tmp++;
if (tmp == d.end())
break;
else if (tmp->num.size() + cur->num.size() <= blockSize * 2)
merge(cur, tmp);
}
}
}
inline void insert(int x, int v) {
register Iterator cur;
register int pos;
find(--x, cur, pos);
cur->num.insert(cur->num.begin() + pos + 1, v);
cur->sorted.insert(
std::lower_bound(cur->sorted.begin(), cur->sorted.end(), v), v);
cur->sum += v;
maintain(cur);
}
inline void erase(int x) {
register Iterator cur;
register int pos, v;
find(--x, cur, pos);
cur->sum -= cur->num[pos];
cur->sorted.erase(std::lower_bound(cur->sorted.begin(), cur->sorted.end(),
cur->num[pos]));
cur->num.erase(cur->num.begin() + pos);
maintain(cur);
}
inline void reverse(int l, int r) {
l--, r--;
std::list<Block> tmp;
Iterator L, R, p;
register int posL, posR;
find(l - 1, L, posL);
if (posL + 1 > 0) split(L, posL + 1), L++;
find(r, R, posR);
split(R, posR + 1);
tmp.splice(tmp.begin(), d, L, ++R);
for (Iterator v = tmp.begin(); v != tmp.end(); v++) v->rev ^= 1;
tmp.reverse();
L = R;
if (L != d.begin()) L--;
d.splice(R, tmp);
maintain(L);
}
inline void revolve(int l, int r, int k) {
l--, r--;
std::list<Block> tmp;
Iterator L, R, p, K;
register int posL, posR, posK;
find(l - 1, L, posL);
if (posL + 1 > 0) split(L, posL + 1), L++;
find(r - k, K, posK);
if (posK + 1 > 0) split(K, posK + 1), K++;
find(r, R, posR);
split(R, posR + 1);
tmp.splice(tmp.begin(), d, K, ++R);
p = L;
if (p != d.begin())
p--;
else
p = d.end();
d.splice(L, tmp);
maintain(p == d.end() ? d.begin() : p);
}
inline void add(int l, int r, int v) {
l--, r--;
Iterator L, R;
register int posL, posR;
find(l, L, posL), find(r, R, posR);
if (L == R) {
L->pushDown();
for (register int i = posL; i <= posR; i++) L->num[i] += v;
L->sum += (posR - posL + 1ll) * v;
L->sorted.assign(L->num.begin(), L->num.end());
std::sort(L->sorted.begin(), L->sorted.end());
} else {
if (posL > 0) {
L->pushDown();
for (register int i = posL; i < L->num.size(); i++) L->num[i] += v;
L->sum += (L->num.size() - posL) * (long)v;
L->sorted.assign(L->num.begin(), L->num.end());
std::sort(L->sorted.begin(), L->sorted.end());
L++;
}
for (; L != R; L++) {
if (L->cover)
L->cover += v;
else
L->delta += v;
}
R->pushDown();
for (register int i = 0; i <= posR; i++) R->num[i] += v;
R->sum += (posR + 1) * v;
R->sorted.assign(R->num.begin(), R->num.end());
std::sort(R->sorted.begin(), R->sorted.end());
}
}
inline void cover(int l, int r, int v) {
l--, r--;
Iterator L, R;
register int posL, posR;
find(l, L, posL), find(r, R, posR);
if (L == R) {
L->pushDown();
for (register int i = posL; i <= posR; i++)
L->sum += v - L->num[i], L->num[i] = v;
L->sorted.assign(L->num.begin(), L->num.end());
std::sort(L->sorted.begin(), L->sorted.end());
} else {
if (posL > 0) {
L->pushDown();
for (register int i = posL; i < L->num.size(); i++)
L->sum += v - L->num[i], L->num[i] = v;
L->sorted.assign(L->num.begin(), L->num.end());
std::sort(L->sorted.begin(), L->sorted.end());
L++;
}
for (; L != R; L++) {
if (L->delta) L->delta = 0;
L->cover = v;
}
R->pushDown();
for (register int i = 0; i <= posR; i++)
R->sum += v - R->num[i], R->num[i] = v;
R->sorted.assign(R->num.begin(), R->num.end());
std::sort(R->sorted.begin(), R->sorted.end());
}
}
inline long querySum(int l, int r) {
l--, r--;
Iterator L, R;
register int posL, posR;
register long ret = 0;
find(l, L, posL), find(r, R, posR);
if (L == R) {
L->pushDown();
for (register int i = posL; i <= posR; i++) ret += L->num[i];
return ret;
} else {
if (posL > 0) {
L->pushDown();
for (register int i = posL; i < L->num.size(); i++)
ret += L->num[i];
L++;
}
for (; L != R; L++) {
ret += L->getSum();
}
R->pushDown();
for (register int i = 0; i <= posR; i++) ret += R->num[i];
return ret;
}
}
inline long queryDiff(int l, int r) {
l--, r--;
Iterator L, R;
register int posL, posR;
register long min = LLONG_MAX, max = LLONG_MIN;
find(l, L, posL), find(r, R, posR);
if (L == R) {
L->pushDown();
for (register int i = posL; i <= posR; i++) {
min = std::min(min, (long)L->num[i]);
max = std::max(max, (long)L->num[i]);
}
return max - min;
} else {
if (posL > 0) {
L->pushDown();
for (register int i = posL; i < L->num.size(); i++) {
min = std::min(min, (long)L->num[i]);
max = std::max(max, (long)L->num[i]);
}
L++;
}
for (; L != R; L++) {
min = std::min(min, L->getMin());
max = std::max(max, L->getMax());
}
R->pushDown();
for (register int i = 0; i <= posR; i++) {
min = std::min(min, (long)L->num[i]);
max = std::max(max, (long)L->num[i]);
}
return max - min;
}
}
inline long queryAbs(int l, int r, int v) {
register long ret = LLONG_MAX;
l--, r--;
Iterator L, R;
register int posL, posR;
find(l, L, posL), find(r, R, posR);
if (L == R) {
L->pushDown();
for (register int i = posL; i <= posR; i++)
ret = std::min(ret, llabs(L->num[i] - v));
return ret;
} else {
if (posL > 0) {
L->pushDown();
for (register int i = posL; i < L->num.size(); i++)
ret = std::min(ret, llabs(L->num[i] - v));
L++;
}
register int tmp, pos;
for (; L != R; L++) {
if (L->cover) {
ret = std::min(ret, llabs(L->cover - v));
continue;
}
tmp = v - L->delta;
pos = std::lower_bound(L->sorted.begin(), L->sorted.end(), tmp) -
L->sorted.begin();
if (pos < L->sorted.size())
ret = std::min(ret, (long)L->sorted[pos] - tmp);
if (pos) ret = std::min(ret, (long)tmp - L->sorted[pos - 1]);
}
R->pushDown();
for (register int i = 0; i <= posR; i++)
ret = std::min(ret, llabs(R->num[i] - v));
return ret;
}
}
inline long queryRank(int l, int r, int v) {
l--, r--;
Iterator L, R;
register int posL, posR;
register int ret = 0;
find(l, L, posL), find(r, R, posR);
if (L == R) {
L->pushDown();
for (register int i = posL; i <= posR; i++) ret += (L->num[i] < v);
return ret;
} else {
if (posL > 0) {
L->pushDown();
for (register int i = posL; i < L->num.size(); i++)
ret += (L->num[i] < v);
L++;
}
register int tmp;
for (; L != R; L++) {
if (L->cover) {
if (L->cover < v) ret += L->num.size();
continue;
}
tmp = v - L->delta;
ret += std::lower_bound(L->sorted.begin(), L->sorted.end(), tmp) -
L->sorted.begin();
}
R->pushDown();
for (register int i = 0; i <= posR; i++) ret += (R->num[i] < v);
return ret;
}
}
inline int divide(std::vector<int> &val, int l, int r, int x) {
l--;
for (register int mid; r - l > 1;) {
mid = l + r >> 1;
if (val[mid] <= x)
l = mid;
else
r = mid;
}
return l;
}
inline int check(Iterator L, Iterator R, int val) {
Iterator ptr = L;
register int cnt = 0, pos, tmp;
if (R != d.end()) R++;
do {
if (ptr->cover) {
if (ptr->cover <= val) cnt += ptr->sorted.size();
ptr++;
continue;
}
tmp = val - ptr->delta;
pos = divide(ptr->sorted, 0, ptr->sorted.size(), tmp);
cnt += pos + 1;
ptr++;
} while (ptr != R);
return cnt;
}
inline long getGlobalMax() {
register long max = LLONG_MIN;
for (Iterator p = d.begin(); p != d.end(); p++)
max = std::max(max, p->getMax());
return max;
}
inline long querySelect(int left, int right, int k) {
left--, right--;
Iterator L, R, ptr;
register int posL, posR, pos;
register long l, r, mid;
find(left - 1, L, posL);
if (posL + 1 > 0) split(L, posL + 1), L++;
find(right, R, posR);
split(R, posR + 1);
l = 0;
r = getGlobalMax();
while (l != r) {
mid = (l + r) >> 1;
if (check(L, R, mid) >= k)
r = mid;
else
l = mid + 1;
}
maintain(L);
return l;
}
#ifdef DBG
// for gdb
void debugPrint(const int x) { std::cerr << x << ' '; }
void showNum(Iterator it) {
it->pushDown();
std::for_each(it->num.begin(), it->num.end(), debugPrint);
std::endl(std::cerr);
}
void showSorted(Iterator it) {
it->pushDown();
std::for_each(it->sorted.begin(), it->sorted.end(), debugPrint);
std::endl(std::cerr);
}
void showAll(Iterator it) { showNum(it), showSorted(it); }
void showBlockListNum() {
std::cerr << "showBlockListNum begin" << std::endl;
for (Iterator it = d.begin(); it != d.end(); it++) showNum(it);
std::cerr << "showBlockListNum done" << std::endl << std::endl;
}
void showBlockListSorted() {
std::cerr << "showBlockListSorted begin" << std::endl;
for (Iterator it = d.begin(); it != d.end(); it++) showSorted(it);
std::cerr << "showBlockListSorted done" << std::endl << std::endl;
}
void showBlockListAll() {
std::cerr << "showBlockListAll begin" << std::endl;
for (Iterator it = d.begin(); it != d.end(); it++) showAll(it);
std::cerr << "showBlockListAll done" << std::endl << std::endl;
}
Iterator getBlock(int k) {
Iterator it = d.begin();
for (register int i = 0; i < k; i++) it->pushDown(), it++;
return it;
}
#endif
inline void solve() {
register int n, m;
io >> n;
static int a[MAXN];
for (register int i = 0; i < n; i++) io >> a[i];
build(a, n);
io >> m;
for (register int cmd, x, y, v, k; m--;) {
io >> cmd;
switch (cmd) {
case 1: {
io >> x >> v;
insert(x, v);
break;
}
case 2: {
io >> x;
erase(x);
break;
}
case 3: {
io >> x >> y;
reverse(x, y);
break;
}
case 4: {
io >> x >> y >> k;
revolve(x, y, k);
break;
}
case 5: {
io >> x >> y >> v;
add(x, y, v);
break;
}
case 6: {
io >> x >> y >> v;
cover(x, y, v);
break;
}
case 7: {
io >> x >> y;
io << querySum(x, y) << '\n';
break;
}
case 8: {
io >> x >> y;
io << queryDiff(x, y) << '\n';
break;
}
case 9: {
io >> x >> y >> v;
io << queryAbs(x, y, v) << '\n';
break;
}
case 10: {
io >> x >> y >> k;
io << querySelect(x, y, k) << '\n';
break;
}
case 11: {
io >> x >> y >> v;
io << queryRank(x, y, v) << '\n';
break;
}
}
}
}
#undef long
}
int main() {
#ifdef DBG
freopen("sample/1.in", "r", stdin);
#endif
solve();
return 0;
}

分享到