QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#451518 | #7872. 崩坏天际线 | zqs | 100 ✓ | 1825ms | 21916kb | C++14 | 5.7kb | 2024-06-23 16:03:12 | 2024-06-23 16:03:12 |
Judging History
answer
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using std::min; using std::swap;
const int mod = 998244353, B = 200, N = 50005;
inline void add(int &x, const int y) {if ((x += y) >= mod) x -= mod;}
inline int plus(const int x, const int y) {return x + y < mod ? x + y : x + y - mod;}
int al[N], ar[N], op[N], p2[N], a[B + 5], tme[B + 5], n, q, ans;
int bl[B * B + 5], br[B * B + 5], bp[B * B + 5], cl[B + 5], cr[B + 5], stk[B + 5], cnt;
struct node {int ls, rs, sum, tag;} tr[2500005];
int id[N], pre[N], nxt[N], len[N];
bool vis[N], ban[N];
std::vector<int> vec[50005];
struct RMQ {
int st[17][50005], Log[50005];
void clear() {memset(st[0], 0x3f, sizeof st[0]);}
void set(int x, int v) {st[0][x] = v;}
void init() {
for (int i = 2; i <= n; ++ i) Log[i] = Log[i >> 1] + 1;
for (int i = 1; i <= 15; ++ i)
for (int j = 1; j + (1 << i) - 1 <= n; ++ j)
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}
int query(int l, int r) {
if (l > r) return q + 1;
int k = Log[r - l + 1];
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
} rmq;
int prob[N], rt1[N], rt2[N], tot;
void spread(int p) {
if (!tr[p].tag) return;
int ls = tr[p].ls, rs = tr[p].rs, tmp = tr[p].tag; tr[p].tag = 0;
if (ls) tr[ls].sum = 1ll * tr[ls].sum * p2[tmp] % mod, tr[ls].tag += tmp;
if (rs) tr[rs].sum = 1ll * tr[rs].sum * p2[tmp] % mod, tr[rs].tag += tmp;
}
void insert(int &p, int l, int r, int x, int v) {
if (!p) p = ++ tot, tr[p].ls = tr[p].rs = tr[p].sum = tr[p].tag = 0;
add(tr[p].sum, v); if (l == r) return;
int mid = l + r >> 1; spread(p);
x <= mid ? insert(tr[p].ls, l, mid, x, v) : insert(tr[p].rs, mid + 1, r, x, v);
}
void pushup(int p) {if (p) tr[p].sum = plus(tr[tr[p].ls].sum, tr[tr[p].rs].sum);}
void split(int &x, int &y, int l, int r, int k) {
if (!x || r <= k) return;
if (k < l) {y = x, x = 0; return;}
spread(x);
int mid = l + r >> 1, z = 0; tr[y = ++ tot].tag = 0;
if (k <= mid) {
split(tr[x].ls, z, l, mid, k), tr[y].ls = z, tr[y].rs = tr[x].rs, tr[x].rs = 0;
} else split(tr[x].rs, z, mid + 1, r, k), tr[y].ls = 0, tr[y].rs = z;
pushup(x), pushup(y);
}
void query(int p, int l, int r, int x) {
if (!p) return;
if (l == r) {ans = (ans + 1ll * abs(x - l) * tr[p].sum) % mod; return;}
spread(p);
query(tr[p].ls, l, l + r >> 1, x), query(tr[p].rs, (l + r >> 1) + 1, r, x);
}
void solve(int st) {
memset(pre, 0, sizeof pre), memset(nxt, 0, sizeof nxt);
memset(prob, 0, sizeof prob), memset(vis, 0, sizeof vis);
memset(ban, 0, sizeof ban), rmq.clear();
for (int i = q; i >= st; -- i) if (op[i] == 2) rmq.set(al[i], i);
rmq.init(), tot = 0;
for (int i = 1; i <= n; ++ i) vec[i].clear(), rt1[i] = rt2[i] = 0;
for (int i = 1; i <= cnt; ++ i) {
int fst = rmq.query(bl[i] + 1, br[i] - 1);
if (fst > q) ans = (ans + 1ll * bp[i] * (br[i] - bl[i])) % mod;
else vec[al[fst]].emplace_back(i);
}
for (int i = st; i <= q; ++ i)
if (op[i] == 2) {if (vis[al[i]]) ban[i] = true; else vis[al[i]] = true;}
for (int i = 1, j = 0; i <= n; ++ i)
if (vis[i]) pre[i] = j, nxt[j] = i, len[j] = i - j, j = i;
pre[0] = nxt[0] = 0;
for (int i = q; i >= st; -- i) if (op[i] == 2 && !ban[i]) {
int x = al[i];
if (pre[x]) nxt[pre[x]] = nxt[x];
if (nxt[x]) pre[nxt[x]] = pre[x];
}
for (int i = st; i <= q; ++ i) if (op[i] == 2 && !ban[i]) {
int x = al[i], l = pre[x], r = nxt[x];
if (r) {
split(rt1[r], rt1[x], 1, n, x - 1), swap(rt1[r], rt1[x]);
if (rt1[x]) tr[rt1[x]].sum = 1ll * tr[rt1[x]].sum * p2[1] % mod, ++ tr[rt1[x]].tag;
}
if (l) {
split(rt2[l], rt2[x], 1, n, x);
if (rt2[x]) tr[rt2[x]].sum = 1ll * tr[rt2[x]].sum * p2[1] % mod, ++ tr[rt2[x]].tag;
}
prob[x] = (1ll * prob[l] * p2[1] + tr[rt1[x]].sum) % mod;
prob[l] = (1ll * prob[l] * p2[1] + tr[rt2[x]].sum) % mod;
for (int j : vec[x]) {
insert(rt1[x], 1, n, bl[j], 1ll * bp[j] * p2[1] % mod);
insert(rt2[x], 1, n, br[j], 1ll * bp[j] * p2[1] % mod);
}
}
for (int i = 1; i <= n; ++ i) {
if (prob[i]) ans = (ans + 1ll * len[i] * prob[i]) % mod;
if (rt1[i]) query(rt1[i], 1, n, i);
if (rt2[i]) query(rt2[i], 1, n, i);
}
}
int main() {
scanf("%d%d", &n, &q);
p2[0] = 1, p2[1] = mod + 1 >> 1;
for (int i = 1; i <= q; ++ i) {
scanf("%d%d", op + i, al + i); if (op[i] == 1) scanf("%d", ar + i);
}
for (int i = 2; i <= q; ++ i) p2[i] = 1ll * p2[1] * p2[i - 1] % mod;
for (int i = 1; i <= (q + B - 1) / B; ++ i) {
int st = (i - 1) * B + 1, ed = min(q, i * B), m = 0;
cnt = 0;
for (int j = ed; j >= st; -- j) {
if (op[j] == 2) {
int pos = m + 1;
for (int k = 1; k <= m; ++ k)
if (a[k] > al[j]) {pos = k; break;}
else if (a[k] == al[j]) {pos = 0, tme[k] = j; break;}
if (pos) {
++ m;
for (int k = m; k > pos; -- k) a[k] = a[k - 1], tme[k] = tme[k - 1];
a[pos] = al[j], tme[pos] = j;
}
} else {
int l = m + 1, r = 0;
for (int k = 1; k <= m; ++ k) if (a[k] > al[j]) {l = k; break;}
for (int k = m; k; -- k) if (a[k] < ar[j]) {r = k; break;}
if (l > r) {bl[++ cnt] = al[j], br[cnt] = ar[j], bp[cnt] = 1; continue;}
for (int k = l, top = 0; k <= r; ++ k) {
while (top && tme[stk[top]] > tme[k]) -- top;
stk[++ top] = k, cl[k] = top;
}
for (int k = r, top = 0; k >= l; -- k) {
while (top && tme[stk[top]] > tme[k]) -- top;
stk[++ top] = k, cr[k] = top;
}
for (int k = l; k < r; ++ k)
bl[++ cnt] = a[k], br[cnt] = a[k + 1], bp[cnt] = p2[cl[k] + cr[k + 1]];
bl[++ cnt] = al[j], br[cnt] = a[l], bp[cnt] = p2[cr[l]];
bl[++ cnt] = a[r], br[cnt] = ar[j], bp[cnt] = p2[cl[r]];
}
}
solve(ed + 1);
}
printf("%d", ans);
return 0;
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 2ms
memory: 10564kb
input:
500 500 1 119 258 2 134 2 417 2 176 2 61 2 60 2 110 1 335 336 1 96 111 2 202 1 138 344 2 358 2 134 1 29 54 1 73 381 1 179 495 2 490 2 418 2 186 2 183 1 168 340 2 78 1 15 27 2 373 1 245 498 1 372 495 2 244 2 63 1 174 490 2 282 2 417 1 272 408 1 109 134 2 303 2 345 1 238 401 1 36 480 1 21 483 2 10 1 3...
output:
855279801
result:
ok single line: '855279801'
Test #2:
score: 0
Accepted
time: 0ms
memory: 10564kb
input:
495 466 1 35 393 2 236 1 4 335 2 455 1 36 470 1 23 61 2 195 2 109 2 451 1 282 491 2 238 2 117 2 468 1 2 60 1 439 487 2 238 1 209 294 2 321 2 309 1 113 183 2 409 2 87 2 130 2 124 2 176 2 448 2 379 1 181 446 2 146 2 450 1 171 423 2 355 2 332 1 123 387 1 151 269 1 17 417 2 122 1 324 494 1 265 439 2 225...
output:
294468977
result:
ok single line: '294468977'
Test #3:
score: 0
Accepted
time: 0ms
memory: 10204kb
input:
441 467 2 180 1 51 344 2 180 1 16 345 1 39 419 1 64 432 2 176 1 35 372 2 426 1 8 415 1 1 439 1 17 430 2 433 1 89 369 1 83 353 2 292 1 1 421 1 63 430 1 33 345 1 69 421 1 49 373 1 77 343 1 24 393 1 90 375 1 8 425 2 322 2 61 2 112 2 209 1 39 406 1 12 426 1 29 430 1 50 374 1 47 394 1 9 387 2 234 1 19 35...
output:
526117259
result:
ok single line: '526117259'
Test #4:
score: 0
Accepted
time: 0ms
memory: 12472kb
input:
500 500 2 442 1 12 414 1 40 435 2 138 1 79 448 1 16 464 2 163 1 94 492 2 97 2 335 1 7 452 1 25 474 1 78 442 2 286 1 93 430 1 78 438 2 469 2 354 2 270 2 292 2 108 2 301 1 100 480 2 258 1 17 487 2 2 2 409 2 385 2 338 1 83 454 1 41 490 1 95 475 1 43 442 1 66 445 2 406 2 168 1 10 406 2 330 2 20 1 90 491...
output:
810270061
result:
ok single line: '810270061'
Test #5:
score: 0
Accepted
time: 0ms
memory: 12208kb
input:
500 500 1 29 407 1 89 480 1 31 497 1 28 494 1 21 492 1 91 465 1 13 467 1 89 425 1 22 444 1 20 430 1 48 445 1 33 441 1 61 435 1 69 427 1 89 485 1 90 446 1 23 488 1 6 424 1 76 425 1 36 460 1 16 421 1 20 500 1 3 487 1 99 481 1 53 412 1 96 456 1 39 436 1 28 436 1 4 409 1 9 486 1 22 484 1 88 413 1 26 467...
output:
419428992
result:
ok single line: '419428992'
Test #6:
score: 0
Accepted
time: 0ms
memory: 12464kb
input:
500 500 1 85 442 1 20 473 1 10 441 1 31 426 1 95 478 1 60 454 1 54 491 1 97 464 1 14 443 1 88 474 1 28 462 1 97 410 1 99 496 1 96 493 1 62 479 1 12 466 1 64 471 1 43 490 1 50 411 1 85 448 1 48 433 1 30 456 1 39 462 1 46 409 1 63 494 1 39 409 1 36 436 1 27 463 1 37 498 1 69 464 1 8 441 1 99 436 1 84 ...
output:
519347055
result:
ok single line: '519347055'
Subtask #2:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #7:
score: 20
Accepted
time: 20ms
memory: 10956kb
input:
5000 5000 2 2254 2 4832 2 208 1 335 3080 2 481 1 527 3659 1 2645 3803 1 855 3544 2 3824 2 347 1 1567 4426 1 2184 4493 2 142 2 2451 1 995 4170 2 576 2 999 2 2726 1 278 3540 2 3218 1 922 3302 2 3253 2 4161 2 4505 1 4201 4534 1 1827 3540 2 3241 2 1909 2 2667 1 723 2453 2 3123 1 1017 4791 1 2953 3384 1 ...
output:
275175220
result:
ok single line: '275175220'
Test #8:
score: 0
Accepted
time: 15ms
memory: 14480kb
input:
4753 4704 1 589 2183 1 922 2210 2 2885 2 171 2 1597 2 3601 1 1906 4730 1 411 3615 2 1665 1 87 801 2 3525 2 2426 2 2723 1 323 4345 2 3950 2 460 2 4165 1 1156 2642 1 1490 3965 1 329 4081 1 1206 2077 2 4216 1 996 2254 2 2219 2 1035 2 4074 2 714 1 952 2726 2 3097 2 409 1 3320 4713 2 4061 1 1765 2040 1 2...
output:
840227126
result:
ok single line: '840227126'
Test #9:
score: 0
Accepted
time: 11ms
memory: 12596kb
input:
4141 4610 2 3761 2 2872 1 334 3247 1 273 3914 1 307 3651 1 607 4105 1 458 3269 1 270 3782 2 311 1 533 3332 2 2495 1 991 3573 1 376 3593 1 239 3682 1 259 3350 1 213 3380 2 1904 1 591 3512 1 845 3785 1 189 3335 1 817 3362 1 335 3288 2 3633 1 747 3586 2 4062 2 3812 1 487 3333 1 740 4002 1 847 3937 1 53...
output:
597472157
result:
ok single line: '597472157'
Test #10:
score: 0
Accepted
time: 23ms
memory: 12676kb
input:
5000 5000 2 2864 1 473 4676 2 858 2 2672 2 4473 2 800 2 3259 2 470 2 3859 2 2228 1 491 4536 1 700 4378 2 498 1 769 4837 1 80 4861 1 109 4201 1 908 4094 1 9 4706 2 1017 2 737 2 4155 1 270 4290 2 4434 2 1867 1 148 4119 1 299 4194 2 4076 2 1863 2 1570 2 4855 1 1000 4834 1 637 4827 2 1961 2 4518 1 811 4...
output:
251906928
result:
ok single line: '251906928'
Test #11:
score: 0
Accepted
time: 10ms
memory: 7392kb
input:
5000 5000 1 327 4388 1 768 4973 1 438 4243 1 288 4244 1 105 4460 1 862 4894 1 125 4611 1 934 4115 1 631 4349 1 635 4088 1 250 4629 1 873 4204 1 977 4296 1 391 4821 1 107 4589 1 86 4810 1 615 4072 1 221 4113 1 745 4771 1 806 4983 1 675 4334 1 709 4428 1 587 4180 1 494 4949 1 904 4253 1 901 4527 1 717...
output:
845230417
result:
ok single line: '845230417'
Test #12:
score: 0
Accepted
time: 17ms
memory: 10876kb
input:
5000 5000 1 902 4097 1 263 4218 1 502 4305 1 798 4433 1 392 4689 1 479 4006 1 518 4269 1 764 4295 1 48 4834 1 966 4574 1 374 4970 1 950 4925 1 54 4860 1 987 4144 1 448 4504 1 329 4838 1 734 4807 1 403 4387 1 275 4396 1 731 4769 1 206 4348 1 282 4258 1 676 4956 1 274 4943 1 892 4146 1 337 4962 1 798 ...
output:
678724707
result:
ok single line: '678724707'
Subtask #3:
score: 40
Accepted
Test #13:
score: 40
Accepted
time: 1205ms
memory: 16472kb
input:
50000 50000 1 24367 33007 1 14396 42256 1 6375 22327 1 7892 42501 1 10100 37998 1 6284 48524 1 7357 18164 1 16200 46424 1 18972 34131 1 16849 32591 1 1917 3018 1 19897 30272 1 45044 45753 1 18999 25448 1 5167 31033 1 6182 35335 1 7270 37270 1 12651 39965 1 28896 38022 1 13853 35426 1 35516 48244 1 1...
output:
733099543
result:
ok single line: '733099543'
Test #14:
score: 0
Accepted
time: 959ms
memory: 17512kb
input:
49951 43686 1 21796 23464 1 29304 46959 1 5034 41719 1 7779 35334 1 27566 36486 1 20347 26165 1 12508 30387 1 18363 20335 1 8540 21417 1 5728 49086 1 46038 47603 1 10371 15910 1 27293 43572 1 18915 45279 1 7388 48342 1 6802 43746 1 4361 40049 1 41177 43375 1 23287 48354 1 37097 41733 1 2406 11638 1 ...
output:
792296531
result:
ok single line: '792296531'
Test #15:
score: 0
Accepted
time: 481ms
memory: 15380kb
input:
49914 43874 1 8935 40963 1 4425 44317 1 1769 45855 1 2436 40257 1 1778 47216 1 383 42149 1 5398 40732 1 1079 43346 1 6578 41660 1 9689 45985 1 6131 42681 1 8862 47431 1 3979 46189 1 6456 43485 1 2028 46574 1 3802 47787 1 6990 41659 1 9221 41204 1 2271 43554 1 8018 45280 1 9344 43917 1 6623 41152 1 7...
output:
831211412
result:
ok single line: '831211412'
Test #16:
score: 0
Accepted
time: 682ms
memory: 15416kb
input:
50000 50000 1 1310 49344 1 5755 44255 1 3582 41465 1 6800 42160 1 1651 44584 1 7967 44410 1 3116 48795 1 1855 41120 1 27 42294 1 2455 49629 1 4196 42487 1 7070 44542 1 136 42053 1 5715 44222 1 8794 43115 1 4048 45579 1 635 46703 1 9246 41055 1 3678 41276 1 4871 41715 1 1659 44679 1 1639 46392 1 2479...
output:
316801136
result:
ok single line: '316801136'
Test #17:
score: 0
Accepted
time: 579ms
memory: 19336kb
input:
50000 50000 1 8731 40028 1 6575 43815 1 9558 42476 1 7269 47567 1 6597 45567 1 7753 49129 1 9892 47319 1 9438 45710 1 8688 46209 1 75 43653 1 8918 44467 1 2751 43343 1 4433 45172 1 8062 40732 1 3342 41158 1 615 45475 1 7497 44843 1 9201 48262 1 3063 44796 1 9294 48709 1 382 46129 1 5935 48889 1 1195...
output:
680677335
result:
ok single line: '680677335'
Test #18:
score: 0
Accepted
time: 924ms
memory: 21444kb
input:
50000 50000 1 5934 20406 1 21982 32375 1 7064 32616 1 28419 47337 1 28379 31201 1 40915 47773 1 14903 35558 1 2825 43481 1 28451 29178 1 4872 24238 1 5487 6527 1 33950 35231 1 6301 27246 1 3825 16238 1 3823 46254 1 10988 36002 1 6447 8234 1 4758 20500 1 4816 33750 1 3332 3743 1 723 25813 1 6797 4955...
output:
211908161
result:
ok single line: '211908161'
Subtask #4:
score: 30
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #19:
score: 30
Accepted
time: 1396ms
memory: 21636kb
input:
50000 50000 1 23820 35205 1 23204 28152 1 10968 38077 2 26347 1 34065 43744 2 6956 1 12386 31941 1 5586 8700 1 37329 37421 1 13872 49853 1 10054 40143 2 9721 1 3312 36213 1 11745 48452 2 27741 2 37848 2 2566 2 9714 1 38322 48081 2 25675 1 28940 35759 2 11908 1 21501 22242 1 22858 23827 1 13837 25563...
output:
963178931
result:
ok single line: '963178931'
Test #20:
score: 0
Accepted
time: 1358ms
memory: 18584kb
input:
49844 49196 1 14456 32911 1 25807 25848 1 36273 38462 2 906 2 11834 2 1552 2 24305 1 25916 28701 2 15959 2 36578 1 4325 48457 1 25678 44301 2 9794 1 11656 20160 2 22873 2 44228 1 29465 40920 2 24618 2 5092 2 47096 1 8617 18389 1 35678 41207 1 12614 16730 2 23299 2 240 1 1980 46841 2 39602 1 2700 217...
output:
720301477
result:
ok single line: '720301477'
Test #21:
score: 0
Accepted
time: 703ms
memory: 20048kb
input:
40208 47419 1 3878 39147 2 40063 1 5302 30782 1 5676 36573 1 3071 31029 2 37839 1 19 34805 1 8302 36156 2 3219 1 3855 38334 2 28443 2 32961 1 7085 30246 2 26657 1 1197 39431 1 6522 37149 2 2160 1 7638 34260 1 7938 36825 2 31484 2 15343 1 4546 34945 1 8836 39829 2 14331 1 8469 34573 2 38079 1 2851 36...
output:
479455278
result:
ok single line: '479455278'
Test #22:
score: 0
Accepted
time: 1388ms
memory: 21916kb
input:
50000 50000 2 13550 2 36223 2 43206 1 5510 47597 2 6104 2 25632 1 9207 49739 1 8081 48987 1 5850 49093 1 5202 40432 2 44451 1 4973 41354 2 47071 2 37601 1 22 47601 1 2915 47643 2 9535 2 30503 2 37084 1 9914 43003 2 36565 1 6144 45818 1 8675 48820 1 406 45803 2 21625 2 18503 2 34530 1 7996 46583 1 66...
output:
749830221
result:
ok single line: '749830221'
Test #23:
score: 0
Accepted
time: 1825ms
memory: 19528kb
input:
50000 50000 2 13683 2 21410 2 44457 2 43166 2 12830 1 17939 27321 2 36727 1 27602 40953 2 18534 2 15927 2 38517 2 49434 2 41945 2 43511 2 2024 2 23862 2 24358 2 20120 2 28683 2 7467 2 35825 2 1214 2 46879 2 20156 2 6592 2 32224 2 181 1 27585 35166 2 6322 2 21685 2 46456 2 32309 2 10167 1 4022 29619 ...
output:
407055283
result:
ok single line: '407055283'
Test #24:
score: 0
Accepted
time: 1113ms
memory: 19152kb
input:
50000 50000 1 3717 40186 1 9852 44874 1 3429 45225 1 6774 49357 1 2761 49086 1 4497 41804 1 6653 45983 1 8605 45746 1 3439 45258 1 4871 45925 1 8952 49447 1 4846 42095 1 4949 48806 1 5032 49881 1 9094 47754 1 6003 43829 1 1665 41735 1 2596 49349 1 4544 42951 1 8987 47280 1 4031 42116 1 9586 48466 1 ...
output:
257719259
result:
ok single line: '257719259'