1172.md (20336B)
1 Source: https://codeforces.com/blog/entry/67511 2 3 [1173A - Nauuo and Votes](/contest/1173/problem/A "Codeforces Round 564 (Div. 2)") 4 5 Idea: [ouuan](/profile/ouuan "Master ouuan") 6 7 **Tutorial** 8 9 Consider the two edge cases: all the $z$ persons upvote / all the $z$ persons downvote. If the results are the same in these two cases, it is the answer. Otherwise, the result is uncertain. 10 11 **Solution** 12 13 ``` 14 #include <iostream> 15 16 using namespace std; 17 18 const char result[4] = {'+', '-', '0', '?'}; 19 20 int solve(int x, int y) 21 { 22 return x == y ? 2 : x < y; 23 } 24 25 int main() 26 { 27 int x, y, z; 28 29 cin >> x >> y >> z; 30 31 cout << result[solve(x + z, y) == solve(x, y + z) ? solve(x, y) : 3]; 32 33 return 0; 34 } 35 ``` 36 37 [1173B - Nauuo and Chess](/contest/1173/problem/B "Codeforces Round 564 (Div. 2)") 38 39 Idea: [Sulfox](/profile/Sulfox "Grandmaster Sulfox") 40 41 **Tutorial** 42 43 * $m\ge\left\lfloor\frac n 2\right\rfloor+1$ 44 45 Consider the chess pieces $1$ and $n$. 46 47 $\because\begin{cases}|r_1-r_n|+|c_1-c_n|\ge n-1\\|r_1-r_n|\le m-1\\|c_1-c_n|\le m-1\end{cases}$ 48 49 $\therefore m-1+m-1\ge n-1$ 50 51 $\therefore m\ge\frac{n+1}2$ 52 53 $\because m\text{ is an integer}$ 54 55 $\therefore m\ge\left\lfloor\frac n 2\right\rfloor+1$ 56 57 * $m$ can be $\left\lfloor\frac n 2\right\rfloor+1$ 58 59 If we put the $i$-th piece on $(r_i,c_i)$ satisfying $r_i+c_i=i+1$, it is a feasible plan, because $|r_i-r_j|+|c_i-c_j|\ge|r_i+c_i-r_j-c_j|$. 60 61 **Solution** 62 63 ``` 64 #include <cstdio> 65 66 using namespace std; 67 68 int main() 69 { 70 int n, i, ans; 71 72 scanf("%d", &n); 73 ans = n / 2 + 1; 74 75 printf("%d", ans); 76 77 for (i = 1; i <= ans; ++i) printf("\n%d 1", i); 78 for (i = 2; i <= n - ans + 1; ++i) printf("\n%d %d", ans, i); 79 80 return 0; 81 } 82 ``` 83 84 [1172A - Nauuo and Cards](/contest/1172/problem/A "Codeforces Round 564 (Div. 1)") 85 86 Idea: [QAQAutoMaton](/profile/QAQAutoMaton "Grandmaster QAQAutoMaton") 87 88 **Tutorial** 89 90 First, try to finish it without playing any empty cards. 91 92 If that's not possible, the best choice is to play several empty cards in a row, then play from $1$ to $n$. For a card $i$, suppose that it is in the $p_i$-th position in the pile ($p_i=0$ if it is in the hand), you have to play at least $p_i - i + 1$ empty cards. So the answer will be $\max\{p_i-i+1+n\}$. 93 94 **Solution** 95 96 ``` 97 #include <iostream> 98 #include <cstdio> 99 #include <algorithm> 100 101 using namespace std; 102 103 const int N = 200010; 104 105 int n, a[N], b[N], p[N], ans; 106 107 int main() 108 { 109 int i, j; 110 111 scanf("%d", &n); 112 113 for (i = 1; i <= n; ++i) 114 { 115 scanf("%d", a + i); 116 p[a[i]] = 0; 117 } 118 119 for (i = 1; i <= n; ++i) 120 { 121 scanf("%d", b + i); 122 p[b[i]] = i; 123 } 124 125 if (p[1]) 126 { 127 for (i = 2; p[i] == p[1] + i - 1; ++i); 128 if (p[i - 1] == n) 129 { 130 for (j = i; j <= n && p[j] <= j - i; ++j); 131 if (j > n) 132 { 133 printf("%d", n - i + 1); 134 return 0; 135 } 136 } 137 } 138 139 for (i = 1; i <= n; ++i) ans = max(ans, p[i] - i + 1 + n); 140 141 printf("%d", ans); 142 143 return 0; 144 } 145 ``` 146 147 [1172B - Nauuo and Circle](/contest/1172/problem/B "Codeforces Round 564 (Div. 1)") 148 149 Idea: [Sulfox](/profile/Sulfox "Grandmaster Sulfox") 150 151 **Tutorial** 152 153 First, if we choose a node as the root, then each subtree must be in a continuous arc on the circle. Then, we can use DP to solve this problem. 154 155 Let $f_u$ be the number of plans to draw the subtree of $u$, then $f_u=(|son(u)|+[u\ne root])!\prod\limits_{v\in son(u)}f_v$ — choose a position for each subtree and then $u$ itself, then draw the subtrees. However, instead of choosing the position of the root, we suppose the root is on a certain point on the circle, then rotate the circle, thus get the answer: $nf_{root}$. 156 157 In fact, we don't have to write a DP, the answer is $n$ times the product of the factorial of each node's degree ($n\prod\limits_{i = 1}^ndegree[i]!$). 158 159 **Solution** 160 161 ``` 162 #include <iostream> 163 #include <cstdio> 164 165 using namespace std; 166 167 typedef long long ll; 168 169 const int N = 200010; 170 const int mod = 998244353; 171 172 int n, ans, d[N]; 173 174 int main() 175 { 176 int i, u, v; 177 178 scanf("%d", &n); 179 ans = n; 180 181 for (i = 1; i < n; ++i) 182 { 183 scanf("%d%d", &u, &v); 184 ans = (ll) ans * (++d[u]) % mod * (++d[v]) % mod; 185 } 186 187 cout << ans; 188 189 return 0; 190 } 191 ``` 192 193 [1172C1 - Nauuo and Pictures (easy version)](/contest/1172/problem/C1 "Codeforces Round 564 (Div. 1)") and [1172C2 - Nauuo and Pictures (hard version)](/contest/1172/problem/C2 "Codeforces Round 564 (Div. 1)") 194 195 Idea: [ouuan](/profile/ouuan "Master ouuan") 196 197 **Tutorial** 198 199 First, let's focus on a single picture with weight $w$ which Nauuo likes, so we only have to know the sum of the weights of the pictures Nauuo likes ($SA=\sum\limits_{i=1}^nw_i[a_i=1]$) and the sum of the disliked ones ($SB=\sum\limits_{i=1}^nw_i[a_i=0]$) instead of all the $n$ weights. 200 201 Then, we can use DP to solve this problem. 202 203 Let $f_w[i][j][k]$ be the expected weight of a picture Nauuo likes with weight $w$ after another $i$ visits since $SA=j$ and $SB=k$. 204 205 Obviously, $f_w[0][j][k]=w$. 206 207 The state transition: 208 209 * The next visit displays the picture we focus on. Probaility: $\frac w{j+k}$. Lead to: $f_{w+1}[i-1][j+1][k]$. 210 * The next visit displays a picture Nauuo likes but is not the one we focus on. Probaility: $\frac{j-w}{j+k}$. Lead to: $f_w[i-1][j+1][k]$. 211 * The next visit displays a picture Nauuo doesn't like. Probaility: $\frac k{j+k}$. Lead to: $f_w[i-1][j][k-1]$. 212 213 So, $f_w[i][j][k]=\frac w{j+k}f_{w+1}[i-1][j+1][k]+\frac{j-w}{j+k}f_w[i-1][j+1][k]+\frac k{j+k}f_w[i-1][j][k-1]$. 214 215 Let $g_w[i][j][k]$ be the expected weight of a picture Nauuo **doesn't like** with weight $w$ after another $i$ visits since $SA=j$ and $SB=k$. The state transition is similar. 216 217 Note that $i,\,j,\,k,\,m$ have some relation. In fact we can let $f'_w[i][j]$ be $f_w[m-i-j][SA+i][SB-j]$ ($SA$ and $SB$ are the initial ones here). 218 219 But up to now, we can only solve the easy version. 220 221 To solve the hard version, let's introduce a lemma: 222 223 $f_w[i][j][k]=wf_1[i][j][k]$ 224 225 Proof: 226 227 Obviously, this is true when $i=0$. 228 229 Then, suppose we have already proved $f_w[i-1][j][k]=wf_1[i-1][j][k]$. 230 231 $\begin{aligned}f_1[i][j][k]&=\frac 1{j+k}f_2[i-1][j+1][k]+\frac{j-1}{j+k}f_1[i-1][j+1][k]+\frac k{j+k}f_1[i-1][j][k-1]\\&=\frac2{j+k}f_1[i-1][j+1][k]+\frac{j-1}{j+k}f_1[i-1][j+1][k]+\frac k{j+k}f_1[i-1][j][k-1]\\&=\frac{j+1}{j+k}f_1[i-1][j+1][k]+\frac k{j+k}f_1[i-1][j][k-1]\end{aligned}$ 232 233 $\begin{aligned}f_w[i][j][k]&=\frac w{j+k}f_{w+1}[i-1][j+1][k]+\frac{j-w}{j+k}f_w[i-1][j+1][k]+\frac k{j+k}f_w[i-1][j][k-1]\\&=\frac{w(w+1)}{j+k}f_1[i-1][j+1][k]+\frac{w(j-w)}{j+k}f_1[i-1][j+1][k]+\frac {wk}{j+k}f_1[i-1][j][k-1]\\&=\frac{w(j+1)}{j+k}f_1[i-1][j+1][k]+\frac {wk}{j+k}f_1[i-1][j][k-1]\\&=wf_1[i][j][k]\end{aligned}$ 234 235 Also, a brief but not so strict proof: the increment in each step is proportional to the expectation. 236 237 So, we only have to calculate $f_1[i][j][k]$ ($f'_1[i][j]$). 238 239 In conclusion: 240 241 $f'_1[i][j]=1\ (i+j=m)$ 242 243 $f'_1[i][j]=\frac{SA+i+1}{SA+SB+i-j}f'_1[i+1][j]+\frac{SB-j}{SA+SB+i-j}f'_1[i][j+1]\ (i+j \lt m)$ 244 245 $g'_1[i][j]=1\ (i+j=m)$ 246 247 $g'_1[i][j]=\frac{SA+i}{SA+SB+i-j}g'_1[i+1][j]+\frac{SB-j-1}{SA+SB+i-j}g'_1[i][j+1]\ (i+j \lt m)$ 248 249 If $a_i=1$, the expected weight of the $i$-th picture is $w_if'_1[0][0]$, otherwise, the expected weight is $w_ig'_1[0][0]$. 250 251 Last question: how to calculate the result modulo $998244353$? 252 253 If you don't know how, please read [the wiki](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) to learn it. 254 255 You can calculate and store all the $\mathcal O(m)$ inverses at first, then you can get an $\mathcal O(n+m^2+m\log p)$ solution instead of $\mathcal O(n+m^2\log p)$ ($p=998244353$ here). 256 257 **Solution** 258 259 ``` 260 #include <cstdio> 261 #include <algorithm> 262 263 using namespace std; 264 265 typedef long long ll; 266 267 const int N = 200010; 268 const int M = 3010; 269 const int mod = 998244353; 270 271 int qpow(int x, int y) //calculate the modular multiplicative inverse 272 { 273 int out = 1; 274 while (y) 275 { 276 if (y & 1) out = (ll) out * x % mod; 277 x = (ll) x * x % mod; 278 y >>= 1; 279 } 280 return out; 281 } 282 283 int n, m, a[N], w[N], f[M][M], g[M][M], inv[M << 1], sum[3]; 284 285 int main() 286 { 287 int i,j; 288 289 scanf("%d%d", &n, &m); 290 291 for (i = 1; i <= n; ++i) scanf("%d", a + i); 292 293 for (i = 1; i <= n; ++i) 294 { 295 scanf("%d", w + i); 296 sum[a[i]] += w[i]; 297 sum[2] += w[i]; 298 } 299 300 for (i = max(0, m - sum[0]); i <= 2 * m; ++i) inv[i] = qpow(sum[2] + i - m, mod - 2); 301 302 for (i = m; i >= 0; --i) 303 { 304 f[i][m - i] = g[i][m - i] = 1; 305 for (j = min(m - i - 1, sum[0]); j >= 0; --j) 306 { 307 f[i][j] = ((ll) (sum[1] + i + 1) * f[i + 1][j] + (ll) (sum[0] - j) * f[i][j + 1]) % mod * inv[i - j + m] % mod; 308 g[i][j] = ((ll) (sum[1] + i) * g[i + 1][j] + (ll) (sum[0] - j - 1) * g[i][j + 1]) % mod * inv[i - j + m] % mod; 309 } 310 } 311 312 for (i = 1; i <= n; ++i) printf("%d\n", int((ll) w[i] * (a[i] ? f[0][0] : g[0][0]) % mod)); 313 314 return 0; 315 } 316 ``` 317 318 [1172D - Nauuo and Portals](/contest/1172/problem/D "Codeforces Round 564 (Div. 1)") 319 320 Idea: [Sulfox](/profile/Sulfox "Grandmaster Sulfox") 321 322 **Tutorial** 323 324 Consider this problem: 325 326 the person in $(i,1)$ facing right is numbered $a_i$, the person in $(1,i)$ facing bottom is numbered $b_i$. The person numbered $p_i$ has to exit the grid from $(i,n)$, the person numbered $q_i$ has to exit the grid from $(n,i)$. 327 328 The original problem can be easily transferred to this problem. And now let's transfer it into an $(n-1)\times (n-1)$ subproblem by satisfying the requirement of the first row and the first column. 329 330 If $a_1=p_1$ and $b_1=q_1$, you can simply do nothing and get an $(n-1)\times (n-1)$ subproblem. 331 332 Otherwise, you can set a portal consisting of two doors in $(x,1)$ and $(1,y)$ where $a_x=p_1$ and $b_y=q_1$. Swap $a_1$ and $a_x$, $b_1$ and $b_y$, then you will get an $(n-1)\times(n-1)$ subproblem. 333 334 Then, you can solve the problem until it changes into a $1\times1$ one. 335 336 This problem can be solved in $\mathcal O(n)$, but the checker needs $\mathcal O(n^2)$. 337 338 **Solution** 339 340 ``` 341 #include <iostream> 342 #include <cstdio> 343 #include <vector> 344 #include <algorithm> 345 346 using namespace std; 347 348 const int N = 1010; 349 350 struct Portal 351 { 352 int x, y, p, q; 353 Portal(int _x, int _y, int _p, int _q): x(_x), y(_y), p(_p), q(_q) {} 354 }; 355 vector<Portal> ans; 356 int n, a[N], b[N], c[N], d[N], ra[N], rb[N], rc[N], rd[N]; 357 358 int main() 359 { 360 int i; 361 362 scanf("%d", &n); 363 364 for (i = 1; i <= n; ++i) 365 { 366 scanf("%d", b + i); 367 rb[b[i]] = i; 368 } 369 for (i = 1; i <= n; ++i) 370 { 371 scanf("%d", a + i); 372 ra[a[i]] = i; 373 } 374 for (i = 1; i <= n; ++i) c[i] = d[i] = rc[i] = rd[i] = i; 375 376 for (i = 1; i < n; ++i) 377 { 378 if (c[i] == ra[i] && d[i] == rb[i]) continue; 379 ans.push_back(Portal(i, rc[ra[i]], rd[rb[i]], i)); 380 int t1 = c[i]; 381 int t2 = d[i]; 382 swap(c[i], c[rc[ra[i]]]); 383 swap(d[i], d[rd[rb[i]]]); 384 swap(rc[ra[i]], rc[t1]); 385 swap(rd[rb[i]], rd[t2]); 386 } 387 388 printf("%d\n", ans.size()); 389 for (auto k : ans) printf("%d %d %d %d\n", k.x, k.y, k.p, k.q); 390 391 return 0; 392 } 393 ``` 394 395 [1172E - Nauuo and ODT](/contest/1172/problem/E "Codeforces Round 564 (Div. 1)") 396 397 Idea: [ODT](/profile/ODT "Master ODT") 398 399 **Tutorial** 400 401 For each color, we can try to maintain the number of simple paths that do not contain such color. 402 403 If we can maintain such information, we can easily calculate the number of simple paths that contain a certain color, thus get the answer. 404 405 For each color, we delete all nodes that belong to such color, thus splitting the tree into some clusters (here we define a "cluster" as a connected subgraph of the original tree). 406 407 By maintaining $\sum\text{cluster size}^2$, we can get the number of simple paths that do not contain such color. 408 409 For each color we try to maintain the same information, add them together, and get the answer. 410 411 So now the problem is: a white tree 412 413 1. reverse the color of a node ( white <-> black ) 414 2. output $\sum\text{cluster size}^2$ 415 416 This problem can be solved by many data structures like top tree, link/cut tree or heavy path decomposition. 417 418 Let's use the link/cut tree for example. 419 420 You can maintain the size of each subtree and the sum of $\text{size}^2$ of each node's sons. Link/cut one node with its father (choose a node as the root and make the tree a rooted-tree first) when its color changes. In this way, the real clusters are the ones that are still connected after deleting the top node of a cluster in the link/cut tree. Update $\sum\text{cluster size}^2$ while linking/cutting. 421 422  423 424 link: 425 426  427 428 cut: 429 430  431 432 **Solution** 433 434 ``` 435 #include <algorithm> 436 #include <cctype> 437 #include <cstdio> 438 #include <cstring> 439 #include <iostream> 440 #include <vector> 441 442 using namespace std; 443 444 typedef long long ll; 445 446 const int N = 400010; 447 448 struct Node 449 { 450 int fa, ch[2], siz, sizi; 451 ll siz2i; 452 ll siz2() { return (ll) siz * siz; } 453 } t[N]; 454 455 bool nroot(int x); 456 void rotate(int x); 457 void Splay(int x); 458 void access(int x); 459 int findroot(int x); 460 void link(int x); 461 void cut(int x); 462 void pushup(int x); 463 464 void add(int u, int v); 465 void dfs(int u); 466 467 int head[N], nxt[N << 1], to[N << 1], cnt; 468 int n, m, c[N], f[N]; 469 ll ans, delta[N]; 470 bool bw[N]; 471 vector<int> mod[N][2]; 472 473 int main() 474 { 475 int i, j, u, v; 476 ll last; 477 478 scanf("%d%d", &n, &m); 479 480 for (i = 1; i <= n; ++i) 481 { 482 scanf("%d", c + i); 483 mod[c[i]][0].push_back(i); 484 mod[c[i]][1].push_back(0); 485 } 486 487 for (i = 1; i <= n + 1; ++i) t[i].siz = 1; 488 489 for (i = 1; i < n; ++i) 490 { 491 scanf("%d%d", &u, &v); 492 add(u, v); 493 add(v, u); 494 } 495 496 for (i = 1; i <= m; ++i) 497 { 498 scanf("%d%d", &u, &v); 499 mod[c[u]][0].push_back(u); 500 mod[c[u]][1].push_back(i); 501 c[u] = v; 502 mod[v][0].push_back(u); 503 mod[v][1].push_back(i); 504 } 505 506 f[1] = n + 1; 507 dfs(1); 508 509 for (i = 1; i <= n; ++i) link(i); 510 511 for (i = 1; i <= n; ++i) 512 { 513 if (!mod[i][0].size()) 514 { 515 delta[0] += (ll)n * n; 516 continue; 517 } 518 if (mod[i][1][0]) 519 { 520 delta[0] += (ll)n * n; 521 last = (ll)n * n; 522 } else 523 last = 0; 524 for (j = 0; j < mod[i][0].size(); ++j) 525 { 526 u = mod[i][0][j]; 527 if (bw[u] ^= 1) 528 cut(u); 529 else 530 link(u); 531 if (j == mod[i][0].size() - 1 || mod[i][1][j + 1] != mod[i][1][j]) 532 { 533 delta[mod[i][1][j]] += ans - last; 534 last = ans; 535 } 536 } 537 for (j = mod[i][0].size() - 1; ~j; --j) 538 { 539 u = mod[i][0][j]; 540 if (bw[u] ^= 1) 541 cut(u); 542 else 543 link(u); 544 } 545 } 546 547 ans = (ll) n * n * n; 548 for (i = 0; i <= m; ++i) 549 { 550 ans -= delta[i]; 551 printf("%I64d ", ans); 552 } 553 554 return 0; 555 } 556 557 bool nroot(int x) { return x == t[t[x].fa].ch[0] || x == t[t[x].fa].ch[1]; } 558 559 void rotate(int x) 560 { 561 int y = t[x].fa; 562 int z = t[y].fa; 563 int k = x == t[y].ch[1]; 564 if (nroot(y)) t[z].ch[y == t[z].ch[1]] = x; 565 t[x].fa = z; 566 t[y].ch[k] = t[x].ch[k ^ 1]; 567 t[t[x].ch[k ^ 1]].fa = y; 568 t[x].ch[k ^ 1] = y; 569 t[y].fa = x; 570 pushup(y); 571 pushup(x); 572 } 573 574 void Splay(int x) 575 { 576 while (nroot(x)) 577 { 578 int y = t[x].fa; 579 int z = t[y].fa; 580 if (nroot(y)) (x == t[y].ch[1]) ^ (y == t[z].ch[1]) ? rotate(x) : rotate(y); 581 rotate(x); 582 } 583 } 584 585 void access(int x) 586 { 587 for (int y = 0; x; x = t[y = x].fa) 588 { 589 Splay(x); 590 t[x].sizi += t[t[x].ch[1]].siz; 591 t[x].sizi -= t[y].siz; 592 t[x].siz2i += t[t[x].ch[1]].siz2(); 593 t[x].siz2i -= t[y].siz2(); 594 t[x].ch[1] = y; 595 pushup(x); 596 } 597 } 598 599 int findroot(int x) 600 { 601 access(x); 602 Splay(x); 603 while (t[x].ch[0]) x = t[x].ch[0]; 604 Splay(x); 605 return x; 606 } 607 608 void link(int x) 609 { 610 int y = f[x]; 611 Splay(x); 612 ans -= t[x].siz2i + t[t[x].ch[1]].siz2(); 613 int z = findroot(y); 614 access(x); 615 Splay(z); 616 ans -= t[t[z].ch[1]].siz2(); 617 t[x].fa = y; 618 Splay(y); 619 t[y].sizi += t[x].siz; 620 t[y].siz2i += t[x].siz2(); 621 pushup(y); 622 access(x); 623 Splay(z); 624 ans += t[t[z].ch[1]].siz2(); 625 } 626 627 void cut(int x) 628 { 629 int y = f[x]; 630 access(x); 631 ans += t[x].siz2i; 632 int z = findroot(y); 633 access(x); 634 Splay(z); 635 ans -= t[t[z].ch[1]].siz2(); 636 Splay(x); 637 t[x].ch[0] = t[t[x].ch[0]].fa = 0; 638 pushup(x); 639 Splay(z); 640 ans += t[t[z].ch[1]].siz2(); 641 } 642 643 void pushup(int x) 644 { 645 t[x].siz = t[t[x].ch[0]].siz + t[t[x].ch[1]].siz + t[x].sizi + 1; 646 } 647 648 void add(int u, int v) 649 { 650 nxt[++cnt] = head[u]; 651 head[u] = cnt; 652 to[cnt] = v; 653 } 654 655 void dfs(int u) 656 { 657 int i, v; 658 for (i = head[u]; i; i = nxt[i]) 659 { 660 v = to[i]; 661 if (v != f[u]) 662 { 663 f[v] = u; 664 dfs(v); 665 } 666 } 667 } 668 ``` 669 670 [1172F - Nauuo and Bug](/contest/1172/problem/F "Codeforces Round 564 (Div. 1)") 671 672 Idea: [rushcheyo](/profile/rushcheyo "Master rushcheyo") 673 674 **Tutorial** 675 676 At first, let's solve this problem in $\mathcal{O}(n\sqrt{n \log n})$. 677 678 Let's split our array into blocks by $B$ integers, and let's find a function, $f(x) = $ which value you will get at the end of the current block if you will start with $x$. With simple induction, you can prove that this function is a piece-wise linear, and it has $\mathcal{O}(B)$ segments, so you can build it iteratively in $\mathcal{O}(B^2)$ time for each block, so the preprocessing took $\mathcal{O}(nB)$. 679 680 And to answer the query, you can keep the current value of $x$ and then find with binary search by that piece-wise linear function the $f(x)$ for the current block. 681 682 With a good choice of $B$, this solution will work in $\mathcal{O}(n\sqrt{n \log n})$. 683 684 Ok, but then how to solve it in $\mathcal{O}(n \log + q \log^2)$? 685 686 Lemma: each segment of this piece-wise linear function has length at least $p$. 687 688 You can prove it with simple induction. 689 690 And then, with this lemma, it is possible by two functions $f(x)$ of size $n$ and $g(x)$ of size $m$ find the new function $h(x) = g(f(x))$, in the $\mathcal{O}(n + m)$, you can do it with two pointers, similar to the previous iterative method, but adding a several points to the function each time, best way to understand it is to check the indendent solution :) 691 692 **Solution** 693 694 ``` 695 #include <bits/stdc++.h> 696 using namespace std; 697 698 typedef long long ll; 699 700 const int N = 1000005; 701 const ll inf = (ll)1e16; 702 int n, m, P, a[N]; 703 ll sum[N]; 704 vector<ll> func[N << 2]; 705 706 vector<ll> merge(int l, int r, int mid, const vector<ll> &f, const vector<ll> &g) { 707 ll suml = sum[mid] - sum[l - 1], sumr = sum[r] - sum[mid]; 708 vector<ll> ret(f.size() + g.size() - 1, inf); 709 for (int i = 0, j = 0; i < (int)f.size(); ++i) { 710 ll xl = f[i], xr = (i + 1 == (int)f.size() ? inf : f[i + 1] - 1), yl = xl + suml - (ll)i * P, yr = xr + suml - (ll)i * P; 711 while (j > 0 && g[j] > yl) --j; 712 while (j < (int)g.size() && (j == 0 || g[j] <= yl)) ++j; 713 --j; 714 for (; j < (int)g.size() && g[j] <= yr; ++j) 715 ret[i + j] = min(ret[i + j], max(xl, g[j] - suml + (ll)i * P)); 716 } 717 ret[0] = -inf; 718 return ret; 719 } 720 void build(int u, int l, int r) { 721 if (l == r) { 722 func[u].push_back(-inf); 723 func[u].push_back(P - a[l]); 724 return; 725 } 726 int mid = l + r >> 1; 727 build(u << 1, l, mid); 728 build(u << 1 | 1, mid + 1, r); 729 func[u] = merge(l, r, mid, func[u << 1], func[u << 1 | 1]); 730 } 731 ll query(int u, int l, int r, int ql, int qr, ll now) { 732 if (l >= ql && r <= qr) 733 return now + sum[r] - sum[l - 1] - (ll)P * (upper_bound(func[u].begin(), func[u].end(), now) - func[u].begin() - 1); 734 int mid = l + r >> 1; 735 if (qr <= mid) 736 return query(u << 1, l, mid, ql, qr, now); 737 if (ql > mid) 738 return query(u << 1 | 1, mid + 1, r, ql, qr, now); 739 return query(u << 1 | 1, mid + 1, r, ql, qr, query(u << 1, l, mid, ql, qr, now)); 740 } 741 742 int main() { 743 scanf("%d%d%d", &n, &m, &P); 744 for (int i = 1; i <= n; ++i) 745 scanf("%d", a + i), sum[i] = sum[i - 1] + a[i]; 746 build(1, 1, n); 747 for (int l, r; m--;) { 748 scanf("%d%d", &l, &r); 749 printf("%I64d\n", query(1, 1, n, l, r, 0)); 750 } 751 return 0; 752 } 753 ``` 754 755 We had prepared a problem similar to [1174F - Ehab and the Big Finale](/contest/1174/problem/F "Codeforces Round 563 (Div. 2)") before that round, so we needed to prepare new problems in four days. It was in such a hurry that there are some imperfections in our round. Please accept our sincere apology.