codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![ ](/predownloaded/de/d7/ded7d3bc2b041c527bebf3c72666cc30c286eb94.png)
    423 
    424 link:
    425 
    426 ![ ](/predownloaded/5c/8a/5c8ab543766958f4ba8236fac7fd2fea4f066afe.png)
    427 
    428 cut:
    429 
    430 ![ ](/predownloaded/11/b0/11b0dec295277e59c5e95ce9df8bab3cfc862837.png)
    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.