codeforces-scrape

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

1581.md (32857B)


      1 Source: https://codeforces.com/blog/entry/95477
      2 
      3 I'm very sorry about all the inconvenience, and I would like to bear the blame. Much thanks to those who help me prepare this round. It's not their fault. And much thanks to your participation.
      4 
      5 ## [1581A - CQXYM Count Permutations](/contest/1581/problem/A "Codeforces Round 745 (Div. 2)")
      6 
      7 idea: [Phantasmagorias](/profile/Phantasmagorias "Master Phantasmagorias")
      8 
      9 preparation: [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
     10 
     11 tutorial: [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
     12 
     13 Assume a permutation $p$, and $\sum_{i=2}^{2n}[p_{i-1} \lt p_i]=k$. Assume a permutaion $q$, satisfying $\forall 1 \leqslant i \leqslant 2n, q_i=2n-p_i$. We can know that $\forall 2 \leqslant i \leqslant 2n,[p_{i-1} \lt p_i]+[q_{i-1} \lt q_i]=1$. Thus,$\sum_{i=2}^{2n}[q_{i-1} \lt q_i]=2n-1-k$, and either $p$ should be counted or $q$ should be counted. All in all, the half of all the permutaions would be counted in the answer. Thus, the answer is $\frac{1}{2}(2n)!$. The time complexity is $O(\sum n)$. If you precalulate the factors, then the complexity will be $O(t+n)$.
     14 
     15 ---
     16 
     17 **solution**
     18 
     19 ```
     20 #include<stdio.h>
     21 int f[100001];
     22 int main(){
     23 	f[1]=1;
     24 	for(register int i=2;i!=100001;i++){
     25 		f[i]=((i<<1)-1ll)*f[i-1]%1000000007*(i<<1)%1000000007;
     26 	}
     27 	int n;
     28 	scanf("%d",&n);
     29 	for(register int i=n;i!=0;i--){
     30 		scanf("%d",&n);
     31 		printf("%d\n",f[n]);
     32 	}
     33 	return 0;
     34 }
     35 ```
     36 
     37 ## [1581B - Diameter of Graph](/contest/1581/problem/B "Codeforces Round 745 (Div. 2)")
     38 
     39 idea: [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
     40 
     41 preparation: [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
     42 
     43 tutorial: [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
     44 
     45 If $m \lt n-1$, the graph can't be connected, so the answer should be `No`.
     46 
     47 If $m \gt \frac{n(n-1)}{2}$, the graph must contaion multiedges, so the answer should be `No`.
     48 
     49 If $m=\frac{n(n-1)}{2}$, the graph must be a complete graph. The diameter of the graph is $1$. If $k \gt 2$ the answer is `YES`, otherwise the answer is `NO`.
     50 
     51 If $n=1$, the graph has only one node, and its diameter is $0$. If $k \gt 1$ the answer is `YES`, otherwise the answer is `NO`.
     52 
     53 If $m=n-1$, the graph must be a tree, the diameter of the tree is at least $2$ when it comes to each node has an edge with node $1$. If $m \gt n-1 \wedge m \lt \frac{n(n-1)}{2}$, we can add edges on the current tree and the diameter wouldn't be more than $2$. Since the graph is not complete graph, the diameter is more than $1$, the diameter is just $2$. If $k \gt 3$ the answer is `YES`, otherwise the answer is `NO`.
     54 
     55 The time complexity is $O(t)$.
     56 
     57 ---
     58 
     59 **solution**
     60 
     61 ```
     62 #include<stdio.h>
     63 inline void Solve(){
     64 	int n,m,k;
     65 	scanf("%d%d%d",&n,&m,&k);
     66 	if((n-1ll)*n>>1<m||m<n-1){
     67 		puts("NO");
     68 		return;
     69 	}
     70 	if(n==1){
     71 		if(k>1){
     72 			puts("YES");
     73 		}else{
     74 			puts("NO");
     75 		}
     76 	}else if(m<(n-1ll)*n>>1){
     77 		if(k>3){
     78 			puts("YES");
     79 		}else{
     80 			puts("NO");
     81 		}
     82 	}else if(k>2){
     83 		puts("YES");
     84 	}else{
     85 		puts("NO");
     86 	}
     87 }
     88 int main(){
     89 	int t;
     90 	scanf("%d",&t);
     91 	for(register int i=0;i!=t;i++){
     92 		Solve();
     93 	}
     94 	return 0;
     95 }
     96 ```
     97 
     98 ## [1580A - Portal](/contest/1580/problem/A "Codeforces Round 745 (Div. 1)")
     99 
    100 idea: [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
    101 
    102 preparation: [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
    103 
    104 tutorial: [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
    105 
    106 We can enumerate the two corner of the submatrix, calculate the answer by precalculating the prefix sums. The time complexity is $O(\sum n^2m^2)$. When we enumerated the upper edge and the lower edge of the submatrix, we can calculate the answer by prefix sum. Assume the left edge of the submatrix is $l$, and the right edge is $r$. The part of anwer contributed by upper and lower edge are two segments, we can calculate the answer by prefix sums. The middle empty part is a submaxtrix, and we can use prefix sums too. Since we have enumerated the upper edge and lower edge, the left edge part is just about $l$, and the right part is just about $r$. Then we enumerate $l$, the answer of the best $r$ can be calculated by precalculating the suffix miniums. The time complexity is $O(\sum{n^2m})$, space complexity is $O(nm)$.
    107 
    108 ---
    109 
    110 **solution**
    111 
    112 ```
    113 #include<stdio.h>
    114 char s[402];
    115 int sum[401][401],f[401];
    116 inline int GetSum(int lx,int ly,int rx,int ry){
    117 	return sum[rx][ry]-sum[rx][ly-1]-sum[lx-1][ry]+sum[lx-1][ly-1];
    118 }
    119 inline void Solve(){
    120 	int n,m,i,j,k,ans=999999,cur;
    121 	scanf("%d%d",&n,&m);
    122 	for(i=1;i<=n;i++){
    123 		scanf("%s",s+1);
    124 		for(j=1;j<=m;j++){
    125 			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(s[j]=='1');
    126 		}
    127 	}
    128 	for(i=1;i!=n;i++){
    129 		for(j=i+4;j<=n;j++){
    130 			for(k=4;k<=m;k++){
    131 				f[k]=GetSum(i+1,1,j-1,k-1)-GetSum(i,1,i,k-1)-GetSum(j,1,j,k-1)-GetSum(i+1,k,j-1,k)+(k<<1)+j-i-3;
    132 			}
    133 			for(k=m-1;k!=3;k--){
    134 				if(f[k+1]<f[k]){
    135 					f[k]=f[k+1];
    136 				}
    137 			}
    138 			for(k=1;k!=m-2;k++){
    139 				cur=f[k+3]-GetSum(i+1,1,j-1,k)+GetSum(i,1,i,k)+GetSum(j,1,j,k)-(k<<1)-GetSum(i+1,k,j-1,k)+j-i-1;
    140 				if(cur<ans){
    141 					ans=cur;
    142 				}
    143 			}
    144 		}
    145 	}
    146 	printf("%d\n",ans);
    147 }
    148 int main(){
    149 	int t;
    150 	scanf("%d",&t);
    151 	while(t!=0){
    152 		Solve();
    153 		t--;
    154 	}
    155 	return 0;
    156 }
    157 ```
    158 
    159 ## [1580B - Mathematics Curriculum](/contest/1580/problem/B "Codeforces Round 745 (Div. 1)")
    160 
    161 idea: [Phantasmagorias](/profile/Phantasmagorias "Master Phantasmagorias")
    162 
    163 preparation: [Phantasmagorias](/profile/Phantasmagorias "Master Phantasmagorias")
    164 
    165 tutorial: [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
    166 
    167 Define the dp state $f_{l,s,d}$ as the number of the permutaion length of $l$ with exactly $d$ such numbers that all the subsegments containing them have exactly $s$ different maxima in total. We enumerate the position of the bigest number in the permutaion. We call the position is $a$. The numbers before $a$ and after $a$ are independent. Then we transform the statement $(l,s,d)$ to $(a-1,x,d+1)$ and $(l-a,y,d+1)$. We also have to distribute the numbers to two parts, so the dp transformation is:
    168 
    169 $f_{l,s,d}=\sum_{a=1}^{l} \binom{l-1}{a-1} \sum_{x=0}^{s}f_{a-1,x,d+1}f_{l-a,s-x-[d=k],d+1}$
    170 
    171 In addition, the answer of the problem is $f_{n,m,k}$. Actually, the dp proccess is just like a cartesian tree. The time complexity is $O(n^2m^2k)$, space complexity is $O(nmk)$. However, it's enough to pass the tests.
    172 
    173 ---
    174 
    175 **solution**
    176 
    177 ```
    178 #include <bits/stdc++.h>
    179 
    180 using namespace std;
    181 
    182 const int MAX_N = 100 + 5;
    183 
    184 int n, m, k, P;
    185 int fac[MAX_N], c[MAX_N][MAX_N], f[MAX_N][MAX_N][MAX_N];
    186 
    187 int add(int a, int b) {
    188     return a + b < P ? a + b : a + b - P;
    189 }
    190 
    191 void dp(int sz, int cnt, int dep) {
    192     if (f[dep][sz][cnt] != -1) return ;
    193     register int &F = f[dep][sz][cnt] = 0;
    194     if (!sz) {
    195         F = 1;
    196         return ;
    197     }
    198     if ((m - dep < 7 && (1 << (m - dep)) < cnt) || (cnt && sz < m - dep)) return ;
    199     if (dep == m) {
    200         F = (cnt == 1 ? fac[sz] : 0);
    201         return ;
    202     }
    203     for (int i = 0; i < sz; i ++) {
    204         register int fi = 0;
    205         register int *fl = f[dep + 1][i], *fr = f[dep + 1][sz - i - 1];
    206         for (int j = max(0, cnt + i + 1 - sz); j <= min(cnt, i); j ++)
    207             if (fl[j] && fr[cnt - j]) {
    208                 dp(i, j, dep + 1);
    209                 dp(sz - i - 1, cnt - j, dep + 1);
    210                 fi = (fi + 1ll * fl[j] * fr[cnt - j]) % P;
    211             }
    212         F = (F + 1ll * fi * c[sz - 1][i]) % P;
    213     }
    214 }
    215 
    216 int main() {
    217     cin >> n >> m >> k >> P; m --;
    218     for (int i = c[0][0] = fac[0] = 1; i <= n; i ++) {
    219         c[i][0] = c[i][i] = 1;
    220         fac[i] = 1ll * fac[i - 1] * i % P;
    221         for (int j = 1; j < i; j ++) c[i][j] = add(c[i - 1][j - 1], c[i - 1][j]);
    222     }
    223     memset(f, -1, sizeof(f));
    224     dp(n, k, 0);
    225     cout << f[0][n][k] << endl;
    226     return 0;
    227 }
    228 ```
    229 
    230 ## [1580C - Train Maintenance](/contest/1580/problem/C "Codeforces Round 745 (Div. 1)")
    231 
    232 idea: [Phantasmagorias](/profile/Phantasmagorias "Master Phantasmagorias")
    233 
    234 preparation: [Phantasmagorias](/profile/Phantasmagorias "Master Phantasmagorias")
    235 
    236 tutorial: [Phantasmagorias](/profile/Phantasmagorias "Master Phantasmagorias") and [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
    237 
    238 Let's distinguish the trains according to $x_i + y_i$.
    239 
    240 If $x_i + y_i \gt \sqrt{m}$, the total times of maintenance and running don't exceed $\frac{m}{\sqrt{m}}=\sqrt{m}$. So we can find every date that the train of model $i$ begin or end maintenance in $O(\sqrt{m})$, and we can maintain a differential sequence. We can add 1 to the beginning date and minus 1 to the end date, and the prefix sum of this sequence is the number of trains in maintenance.
    241 
    242 If $x_i + y_i \le \sqrt{m}$, suppose the train of model $i$ is repaired at $s_i$ day. For a date $t$ that the train of model $i$ is in maintenance if and only if $(t-s_i) \ mod \ (x_i+y_i) \geq x_i$. Thus for each $a \le \sqrt{m}$, we can use an array of length $a$ to record the date of all trains that satisfy $x_i + y_i = a$ are in maintenance modulo $a$. And for one period of maintenance, the total days aren't exceed $\sqrt{m}$. So we can maintain $(t - s_i) \ mod \ (x_i + y_i)$ in $O(\sqrt{m})$.
    243 
    244 Thus the intended time complexity is $O(m\sqrt{m})$ and the intended memory complexity is $O(n + m)$.
    245 
    246 #### Tutorial by [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
    247 
    248 Finished reading the statement, you may have thought about this easy solution as followed. Maintain an array to count the trains in maintenance in each day. For add and remove operations, traverse the array and add the contribution to the array. The algorithm works in the time complexity of $O(nm)$. Besides, we can use the difference array to modify a segment in $O(1)$. However, we can optimize this solution. For the trains of $x+y \gt \sqrt m$, we can modify every period by brute force because the number of periods is less than $\sqrt m$. For the trains of $x+y \leqslant \sqrt m$, the number of the periods can be large. In this case, we set the blocks, each of them sizes $O(\sqrt m)$. We can merge the modifies which are completely included in the same block, with the same length of period and the same start position in the block. It's fine to use an array to record this. Number of segments are not completely included in the block is about $O(\sqrt m)$. The total complexity is $O(m\sqrt m)$.
    249 
    250 ---
    251 
    252 **solution**
    253 
    254 ```
    255 #include <bits/stdc++.h>
    256 
    257 char BUF_R[1 << 22], *csy1, *csy2;
    258 #define GC (csy1 == csy2 && (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, 1 << 22, stdin), csy1 == csy2) ? EOF : *csy1 ++)
    259 
    260 template <typename Ty>
    261 inline void RI(Ty &t) {
    262     char c = GC;
    263     for (t = 0; c < 48 || c > 57; c = GC);
    264     for (; c > 47 && c < 58; c = GC) t = t * 10 + (c ^ 48);
    265 }
    266 
    267 const int MAX_N = 200000 + 5;
    268 const int MAX_M = 256;
    269 int n, m, thre, x[MAX_N], y[MAX_N], cnt[MAX_M][MAX_M], s[MAX_N], a[MAX_N], ans;
    270 
    271 void block_modify(int Tm, int k, int v) {
    272     int bl = x[k] + y[k], *c = cnt[bl];
    273     int l = (Tm + x[k]) % bl, r = (Tm - 1) % bl;
    274     if (l <= r) for (int i = l; i <= r; i ++) c[i] += v;
    275     else {
    276         for (int i = 0; i <= r; i ++) c[i] += v;
    277         for (int i = l; i < bl; i ++) c[i] += v;
    278     }
    279 }
    280 
    281 int block_query(int Tm) {
    282     register int res = 0;
    283     for (int i = 2; i <= thre; i ++) res += cnt[i][Tm % i];
    284     return res;
    285 }
    286 
    287 int main() {
    288     RI(n); RI(m);
    289     thre = std::min((int)(0.5 * sqrt(m)) + 1, 255);
    290     for (int i = 1; i <= n; i ++) {RI(x[i]); RI(y[i]);}
    291     for (int i = 1; i <= m; i ++) {
    292         int opt, k;
    293         RI(opt); RI(k);
    294         if (opt == 1) {
    295             if (thre < x[k] + y[k]) {
    296                 for (int j = i + x[k]; j <= m; j += x[k] + y[k]) {
    297                     a[j] ++;
    298                     if (j + y[k] <= m) a[j + y[k]] --;
    299                 }
    300             }else block_modify(i, k, 1);
    301             s[k] = i;
    302         }else {
    303             if (thre < x[k] + y[k]) {
    304                 for (int j = s[k] + x[k]; j <= m; j += x[k] + y[k]) {
    305                     a[j] --;
    306                     if (j + y[k] <= m) a[j + y[k]] ++;
    307                     if (j < i && j + y[k] >= i) ans --;
    308                 }
    309             }else block_modify(s[k], k, -1);
    310         }
    311         ans += a[i];
    312         printf("%d\n", ans + block_query(i));
    313     }
    314     return 0;
    315 }
    316 ```
    317 
    318 ## [1580D - Subsequence](/contest/1580/problem/D "Codeforces Round 745 (Div. 1)")
    319 
    320 idea: [Phantasmagorias](/profile/Phantasmagorias "Master Phantasmagorias")
    321 
    322 preparation: [Phantasmagorias](/profile/Phantasmagorias "Master Phantasmagorias")
    323 
    324 tutorial: [Phantasmagorias](/profile/Phantasmagorias "Master Phantasmagorias") and [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
    325 
    326 First we can change the way we calculate the value of a subsequence. We can easily see the value of a subsequence $a_{b_1},a_{b_2},\ldots ,a_{b_m}$ is also $\sum_{i = 1}^m \sum_{j = i + 1}^m a_{b_i} + a_{b_j} - 2 \times f(b_i, b_j)$, which is very similar to the distance of two node on a tree. Thus we can build the cartesian tree of the sequence, and set the weight of a edge between node $i$ and $j$ as $|a_i - a_j|$. Then we can see what we are going to calculate turns into follows : choosing $m$ nodes, maximize the total distance between every two nodes. Thus we can solve this task using dynamic programming with the time complexity $O(n^2)$.
    327 
    328 #### Tutorial by [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
    329 
    330 From the statement, we'd calculate the sums like $a_i+a_j-Min_{k=i}^j a_k$. When we put this on a cartesian tree, it turns out to be $a_i+a_j-a_{LCA(i,j)}$. Set the weigth of the edge $x \rightarrow y$ as $a_y-a_x$, $a_i+a_j-a_{LCA(i,j)}$ equals to the distance between node $i,j$ on the tree. Define the dp state $f_{i,j}$ as the maxium answer in the subtree rooted at node $i$, and we choose $j$ of the nodes in the subtree. Enumerate how many nodes we choose in the subtree of left-son of node $i$, number of nodes of right-son, and whether node $i$ is chose. The contribution made by the edge is its weight times the number of nodes are chose. Since a pair of node will contribute time complexity only when we are calculating the dp state of their LCA, the total time complexity is $O(n^2)$.
    331 
    332 ---
    333 
    334 **solution**
    335 
    336 ```
    337 #include <cstdio>
    338 #include <algorithm>
    339 
    340 typedef long long ll;
    341 
    342 const int MAX_N = 4000 + 5;
    343 
    344 int N, M, a[MAX_N], ls[MAX_N], rs[MAX_N], lw[MAX_N], rw[MAX_N], sz[MAX_N];
    345 ll f[MAX_N][MAX_N];
    346 
    347 inline void umax(ll &a, ll b) {
    348     a = a < b ? b : a;
    349 }
    350 
    351 void dfs(int u) {
    352     sz[u] = 1;
    353     if (ls[u]) {
    354         dfs(ls[u]);
    355         for (int i = std::min(M, sz[u]); i >= 0; i --)
    356             for (int j = std::min(M, sz[ls[u]]); j >= 0; j --)
    357                 umax(f[u][i + j], f[u][i] + f[ls[u]][j] + 1ll * j * (M - j) * lw[u]);
    358         sz[u] += sz[ls[u]];
    359     }
    360     if (rs[u]) {
    361         dfs(rs[u]);
    362         for (int i = std::min(M, sz[u]); i >= 0; i --)
    363             for (int j = std::min(M, sz[rs[u]]); j >= 0; j --)
    364                 umax(f[u][i + j], f[u][i] + f[rs[u]][j] + 1ll * j * (M - j) * rw[u]);
    365         sz[u] += sz[rs[u]];
    366     }
    367 }
    368 
    369 int main() {
    370     scanf("%d%d", &N, &M);
    371     static int sta[MAX_N], tp;
    372     for (int i = 1; i <= N; i ++) {
    373         scanf("%d", a + i);
    374         int k = tp;
    375         for (; k && a[i] < a[sta[k]]; k --);
    376         if (k) {
    377             rs[sta[k]] = i;
    378             rw[sta[k]] = a[i] - a[sta[k]];
    379         }
    380         if (k < tp) {
    381             ls[i] = sta[k + 1];
    382             lw[i] = a[sta[k + 1]] - a[i];
    383         }
    384         sta[++ k] = i;
    385         tp = k;
    386     }
    387     dfs(sta[1]);
    388     printf("%lld\n", f[sta[1]][M]);
    389     return 0;
    390 }
    391 ```
    392 
    393 ## [1580E - Railway Construction](/contest/1580/problem/E "Codeforces Round 745 (Div. 1)")
    394 
    395 idea: [Phantasmagorias](/profile/Phantasmagorias "Master Phantasmagorias")
    396 
    397 preparation: [Phantasmagorias](/profile/Phantasmagorias "Master Phantasmagorias")
    398 
    399 tutorial: [Phantasmagorias](/profile/Phantasmagorias "Master Phantasmagorias")
    400 
    401 For convenience, we first define $dis[u]$ as the length of the shortest path between node 1 and node $u$ and "distance" of node $u$ as $dis[u]$, and call node $u$ is "deeper" than node $v$ if and only if $dis[u] \gt dis[v]$. Similarly, we call node $u$ is "lower" than node $v$ if and only if $dis[u] \lt dis[v]$. We will use $u$ -> $v$ to denote a a directed edge staring at node $u$ and ending at node $v$, and use $u$ --> $v$​ to denote an arbitrary path staring at node $u$ and ending at node $v$. We call two paths "intersect" if and only if they pass through at least 1 same node.
    402 
    403 First let's focus on several facts.
    404 
    405 1. Since all edges' weights are positive, and we have to make sure that the distance of every node does not change, for any node $u$​, we can only add edges starting at a node whose distance is strictly less than $dis[u]$. Besides, we can always add edge 1 -> $u$, but we can never add edge $u$ -> 1.
    406 2. Since the distance of every node does not change and the train only pass through the shortest path, if an edge is not on the shortest path at first, however we add edges it won't be on any shortest path. Thus we can first calculate the shortest path and then remove all edges which are not on the shortest path. We can easily see that the new graph is a $DAG$ (Directed Acyclic Graph). And in this graph the topological order is also the ascending order of nodes' distances. In the following part of this tutorial, we will use the new graph instead of the original graph.
    407 3. After we add all edges, every node except node 1 must have at least 2 incoming edges.
    408 
    409 Then let's prove a lemma: if every node except node 1 exactly has 2 incoming edges, the graph will meet the requirement.
    410 
    411 We will use mathematical induction method to prove the lemma. For an arbitrary node $u$, we suppose that all nodes whose distance is less than $u$'s has met the requirement, and we only need to prove that node $u$​ also meets the requirement. Suppose the start of the 2 incoming edges is separately $s$ and $t$.
    412 
    413 First, if $s$ or $t$ is node 1, we can simply choose $1$ --> $u$ and $1$ --> $t$ -> $u$ as the two paths and obviously they don't intersect. Thus it meet the requirement.
    414 
    415 Second, if $s$ and $t$ are not node 1. We choose an arbitrary path $1$ --> $s$ and call it path 0. According to our assumption, we can choose two different paths starting at node 1 and ending at node $t$​, and the two paths don't intersect. We call them path 1 and path 2 separately.
    416 
    417 If path 0 and path 1 (or path 2) doesn't intersect, then we can choose path 0 and path 1 to meet the requirement. Thus we only need to consider the situation that path 0 intersect with both path 1 and path 2.
    418 
    419 In this case, we first find the lowest and deepest node where path 0 and path 1 or path 2 intersect, and call them $a$ and $b$ separately.
    420 
    421 If the both are the intersect points of path 0 and path 1, like the case below, we can choose path (1 -> a -> (through path 1, i.e. blue path) b -> s) and path 2.
    422 
    423 ![ ](/predownloaded/d8/2e/d82ee3d628a11e34809e2b67012673941957a200.png)
    424 
    425 Otherwise, like the case below, we can choose path (1 -> a -> t) and path (1 -> b -> s).
    426 
    427 ![ ](/predownloaded/78/67/7867bc2eda0340261992ce12bc15da0dc98dfa73.png)
    428 
    429 Both cases are meet the requirement.
    430 
    431 Thus we've proved the lemma. So we only need to make sure that every node except node 1 has at least 2 incoming edges. Then we can get the following solution if $w$ is fixed:
    432 
    433 For every node which has only 1 incoming edge, we record the start point of the incoming edge in an array. Then We scan all nodes in the ascending order of nodes' distances, and maintain the previous minima and second minima of $w$​ in an array $val$​, adding edges greedy. Note that we only need to maintain the index of $w$ instead of its real value. This solution consumes $O(n)$ to calculate for a fixed $w$, so the total complexity is $O(nq)$.
    434 
    435 To accelerate the solution, let's try maintaining array $val$ while changing $w$. And we will apply all the changes in reverse order. That is, we only consider the case that $w$ is decreasing.
    436 
    437 According to the value of $val$, we can separate the sequence into many subsegments, and we can use std::set to maintain those subsegments. For one change in $w_k$, it will affect a particular suffix of $val$​, so we can first find the suffix. Then we consecutively change the array $val$​​ until $w_k$​ is greater than current subsegment's second minima. Next we will prove that the solution works in $O((n+q)logn)$.
    438 
    439 When we change a particular subsegment, we separate the operation into 3 types according to the relationship between $w_k$ and the subsegment's $val$.
    440 
    441 1. If $w_k$​​ is exactly the minima of the subsegment. This kind of operation may be done many times, but we will find that it won't change $val$ at all. So we can do them at a time using segment tree. Thus in one change we will only do it at most 1 time.
    442 2. If $w_k$ is the second minima of the subsegment. Note the fact that every subsegment must has different second minima, so this kind of operation will be also done at most once in one change.
    443 3. If $w_k$ is neither the minima nor the second minima of the subsegment. Note the fact that each time we do it, except the first time, will make the number of subsegments decrease by 1. Thus this kind of operation will be done no more than $n+q$ times.
    444 
    445 Using std::set and segment tree, all of these operations could be done in $O(logn)$ at a time. Thus the total complexity is $O((n+q)logn)$.
    446 
    447 In conclusion, we can solve this task in $O(mlogm + (n+q)logn)$.
    448 
    449 ---
    450 
    451 **solution**
    452 
    453 ```
    454 #include <cstdio>
    455 #include <algorithm>
    456 #include <queue>
    457 #include <set>
    458 
    459 using std::set;
    460 
    461 typedef long long ll;
    462 
    463 char BUF_R[1 << 22], *csy1, *csy2;
    464 #define GC (csy1 == csy2 && (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, 1 << 22, stdin), csy1 == csy2) ? EOF : *csy1 ++)
    465 
    466 template <class T>
    467 inline void RI(T &t) {
    468 	char c = GC;
    469 	for (t = 0; c < 48 || c > 57; c = GC);
    470 	for (; c > 47 && c < 58; c = GC) t = t * 10 + (c ^ 48);
    471 }
    472 
    473 const int MAX_N = 200000 + 5;
    474 const int MAX_M = 600000 + 5;
    475 const int INF32 = 0x7fffffff;
    476 const ll INF64 = 0x3fffffffffffffffll;
    477 
    478 int N, M, Q, ques[MAX_N][2];
    479 struct Edge{
    480     int y, prev, len;
    481 }e[MAX_M];
    482 int elast[MAX_N], ecnt = 1;
    483 std::priority_queue < std::pair <ll, int> > pq;
    484 ll dis[MAX_N], w[MAX_N];
    485 unsigned long long res[MAX_N], ans;
    486 int cnt[MAX_N], fa[MAX_N], a[MAX_N], t;
    487 int rt[MAX_N], pos[MAX_N], sum[MAX_N], endpos[MAX_N];
    488 struct Node{
    489     int f, s;
    490     
    491     Node (int a = 0, int b = 0) : f(a), s(b) {}
    492     
    493     inline bool operator == (const Node &comp) const {return f == comp.f && s == comp.s;}
    494     
    495     inline void swap() {
    496         int t = f;
    497         f = s;
    498         s = t;
    499     }
    500 }minv, val[MAX_N];
    501 set <int> s;
    502 
    503 namespace SGT{
    504     const int MAX_M = 10000000;
    505     
    506     int tot;
    507     struct SegmentNode{
    508         int sum, ls, rs;
    509     }node[MAX_M];
    510     
    511     void segment_modify(int &i, int l, int r, int x) {
    512         i = i ? i : ++ tot;
    513         node[i].sum ++;
    514         if (l == r) return ;
    515         int mid = (l + r) >> 1;
    516         mid < x ? segment_modify(node[i].rs, mid + 1, r, x) : segment_modify(node[i].ls, l, mid, x);
    517     }
    518     
    519     int segment_query(int i, int l, int r, int ql, int qr) {
    520         if (!i) return 0;
    521         if (l < ql || r > qr) {
    522             int mid = (l + r) >> 1, res = 0;
    523             if (mid >= ql) res = segment_query(node[i].ls, l, mid, ql, qr);
    524             if (mid < qr) res += segment_query(node[i].rs, mid + 1, r, ql, qr);
    525             return res;
    526         }else return node[i].sum;
    527     }
    528 }
    529 
    530 int count_illegal(int idx, int l, int r) {
    531     if (r < l || idx == 1) return 0;
    532     return SGT::segment_query(rt[idx], 1, N, l, r);
    533 }
    534 
    535 int count_legal(int idx, int l, int r) {
    536     if (r < l) return 0;
    537     return sum[r] - sum[l - 1] - count_illegal(idx, l, r);
    538 }
    539 
    540 void Build(int x, int y, int z) {
    541     ecnt ++;
    542     e[ecnt].y = y;
    543     e[ecnt].len = z;
    544     e[ecnt].prev = elast[x];
    545     elast[x] = ecnt;
    546 }
    547 
    548 int main() {
    549     RI(N); RI(M); RI(Q);
    550     for (int i = 1; i <= N; i ++) {
    551         RI(w[i]);
    552         pos[i] = N + 1;
    553         dis[i] = INF64;
    554     }
    555     for (int i = 1; i <= M; i ++) {
    556         int x, y, z;
    557         RI(x); RI(y); RI(z);
    558         Build(x, y, z);
    559         Build(y, x, z);
    560     }
    561     for (int i = 1; i <= Q; i ++) {
    562         RI(ques[i][0]); RI(ques[i][1]);
    563         w[ques[i][0]] += ques[i][1];
    564     }
    565     
    566     dis[1] = 0;
    567     pq.push(std::make_pair(0, 1));
    568     while (!pq.empty()) {
    569         int u = pq.top().second;
    570         ll d = -pq.top().first;
    571         pq.pop();
    572         if (dis[u] != d) continue;
    573         a[++ t] = u;
    574         for (int i = elast[u]; i; i = e[i].prev) {
    575             int v = e[i].y;
    576             if (d + e[i].len < dis[v]) {
    577                 dis[v] = d + e[i].len;
    578                 pq.push(std::make_pair(-dis[v], v));
    579             }
    580         }
    581     }
    582     for (int i = 2; i <= ecnt; i ++) {
    583         int u = e[i ^ 1].y, v = e[i].y;
    584         if (dis[u] + e[i].len == dis[v]) {
    585             cnt[v] ++; fa[v] = u;
    586         }
    587     }
    588     
    589     ans = 0;
    590     s.insert(1);
    591     pos[1] = 1;
    592     minv.f = 1;
    593     minv.s = N + 1;
    594     val[1] = minv;
    595     w[N + 1] = INF64;
    596     for (int i = 2, j = 2; i <= N; i ++) {
    597         int u = a[i];
    598 		for (; dis[a[j]] < dis[u]; j ++) {
    599 		    int v = a[j];
    600 		    pos[v] = i;
    601     		if (w[v] < w[minv.f]) {
    602     		    s.insert(i);
    603     		    endpos[minv.f] = i;
    604     		    minv.s = minv.f;
    605     		    minv.f = v;
    606     		    val[i] = minv;
    607     		}else if (w[v] < w[minv.s]) {
    608     		    s.insert(i);
    609     		    minv.s = v;
    610     		    val[i] = minv;
    611     		}
    612     	}
    613     	sum[i] = sum[i - 1];
    614         if (cnt[u] < 2) {
    615             sum[i] ++;
    616             if (fa[u] > 1) SGT::segment_modify(rt[fa[u]], 1, N, i);
    617 		    ans += w[(minv.f == 1 || minv.f != fa[u]) ? minv.f : minv.s];
    618 		}
    619     }
    620     endpos[minv.f] = N + 1;
    621     s.insert(N + 1);
    622     res[Q] = ans;
    623     
    624     for (int i = Q; i > 0; i --) {
    625         int k = ques[i][0], x = ques[i][1];
    626         w[k] -= x;
    627         if (pos[k] > N) {
    628             res[i - 1] = ans;
    629             continue;
    630         }
    631         set <int>::iterator it = -- s.upper_bound(pos[k]), lst;
    632         minv = Node();
    633         int response = 0, p = pos[k];
    634         if (k == val[*it].f) response = 1;
    635         else if (k == val[*it].s) response = 2;
    636         while (response >= 0 && *it <= N) {
    637             lst = it ++;
    638             if (response == 0) {
    639                 if (w[val[*lst].s] <= w[k]) break;
    640                 if (w[k] < w[val[*lst].f]) {
    641                     if (!minv.f) endpos[val[*lst].f] = p;
    642                     int c = count_illegal(val[*lst].f, p, (*it) - 1), tot = sum[(*it) - 1] - sum[p - 1];
    643                     ans -= 1ull * c * w[val[*lst].s] + 1ll * (tot - c) * w[val[*lst].f];
    644                     if (p != *lst) val[p] = val[*lst];
    645                     val[p].s = val[p].f;
    646                     val[p].f = k;
    647                     c = count_illegal(k, p, (*it) - 1);
    648                     ans += 1ull * c * w[val[p].s] + 1ll * (tot - c) * w[k];
    649                     if (p != *lst) {
    650                         s.insert(p);
    651                         minv = val[p];
    652                     }else if (minv == val[p]) s.erase(lst);
    653                     else minv = val[p];
    654                     endpos[k] = p = *it;
    655                 }else {
    656                     ans += 1ull * count_illegal(val[*lst].f, p, (*it) - 1) * (w[k] - w[val[*lst].s]);
    657                     if (p != *lst) val[p] = val[*lst];
    658                     val[p].s = k;
    659                     if (p != *lst) {
    660                         s.insert(p);
    661                         minv = val[p];
    662                     }else if (minv == val[p]) s.erase(lst);
    663                     else minv = val[p];
    664                     p = *it;
    665                 }
    666             }else if (response == 1) {
    667                 it = s.lower_bound(endpos[k]);
    668                 ans -= 1ull * count_legal(k, p, (*it) - 1) * x;
    669                 p = *it; lst = it; lst --;
    670                 minv = val[*lst];
    671                 response = val[p].s == k ? 2 : 0;
    672             }else {
    673                 if (w[val[*lst].f] <= w[k]) {
    674                     ans -= 1ull * count_illegal(val[*lst].f, p, (*it) - 1) * x;
    675                     minv = val[*lst]; p = *it;
    676                 }else {
    677                     endpos[val[*lst].f] = p;
    678                     int c = count_illegal(val[*lst].f, p, (*it) - 1), tot = sum[(*it) - 1] - sum[p - 1];
    679                     ans -= 1ull * c * (w[val[*lst].s] + x) + 1ull * (tot - c) * w[val[*lst].f];
    680                     if (p != *lst) val[p] = val[*lst];
    681                     val[p].swap();
    682                     c = count_illegal(val[p].f, p, (*it) - 1);
    683                     ans += 1ull * c * w[val[p].s] + 1ull * (tot - c) * w[val[p].f];
    684                     if (p != *lst) {
    685                         s.insert(p);
    686                         minv = val[p];
    687                     }else if (minv == val[p]) s.erase(lst);
    688                     else minv = val[p];
    689                     endpos[k] = p = *it;
    690                 }
    691                 response = 0;
    692             }
    693         }
    694         res[i - 1] = ans;
    695     }
    696     
    697     for (int i = 0; i <= Q; i ++) printf("%llu\n", res[i]);
    698     
    699     return 0;
    700 }
    701 ```
    702 
    703 ## [1580F - Problems for Codeforces](/contest/1580/problem/F "Codeforces Round 745 (Div. 1)")
    704 
    705 idea: [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
    706 
    707 preparation: [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
    708 
    709 tutorial: [CQXYM](/profile/CQXYM "Grandmaster CQXYM")
    710 
    711 If two numbers $a,b$ satisfying $a+b \lt m$, there can only be one number not less than $\lceil \frac{m}{2} \rceil$. Consider that cut the cycle to a sequence at the first position $p$ satisfying $\max(a_p,a_{p+1}) \lt \lceil \frac{m}{2} \rceil$. When we minus all the numbers that are not less than $\lceil \frac{m}{2} \rceil$ by $\lceil \frac{m}{2} \rceil$, we can get a sub-problem. However, If $n$ is an even number, we may not find such a position $p$, but we can still get a sub-problem easily. For this problem on a sequence, we can divide the sequence into many segments, and each of them can not be cut by us anymore. There may be only $1$ segment, and the first, last element of the segment are not less than $\lceil \frac{m}{2} \rceil$. There may be many segments, the length of the first one and last one are even, and the rest of them are odd. To solve the problem, we define the GF A,B. A is the GF of the length of the segments are odd situation, and B is the even one. If $m$ is odd, the segment with only a number $[\frac{m}{2}]$ exists, and the GF of number of the sequence should be:
    712 
    713 $B^2(\sum_{i=0} (A+x)^i)+A=\frac{B^2}{1-x-A}+A$
    714 
    715 Otherwise, it is:
    716 
    717 $B^2(\sum_{i=0} A^i)+A=\frac{B^2}{1-A}+A$.
    718 
    719 To solve this problem, use NTT and polynomial inversion algorithm is just ok. Each time we transform a problem with limit $m$ to $\frac{m}{2}$, so the time complexity is $O(n \log n \log m)$.
    720 
    721 ---
    722 
    723 **solution**
    724 
    725 ```
    726 #include<stdio.h>
    727 #include<memory.h>
    728 #define mod 998244353
    729 
    730 unsigned long long tmp[131073],invn;
    731 int a_[131072];
    732 
    733 inline int ksm(unsigned long long a,int b){int ans=1;while(b)(b&1)&&(ans=a*ans%mod),a=a*a%mod,b>>=1;return ans;}
    734 void init(int n){
    735 	for(int i=1;i<n;i++)a_[i]=i&1?a_[i^1]|n>>1:a_[i>>1]>>1;
    736 	for(int i=tmp[0]=1,j=ksm(3,(mod-1)/n);i<=n;i++)tmp[i]=tmp[i-1]*j%mod;
    737 	invn=ksm(n,mod-2);
    738 }
    739 void ntt(int a[],int n,bool typ){
    740 	int p;
    741 	for(int i=1;i<n;i++)if(a_[i]<i)p=a[i],a[i]=a[a_[i]],a[a_[i]]=p;
    742 	if(typ)for(int i=1,d=n>>1;d;i<<=1,d>>=1)for(int j=0;j<n;j+=i<<1)for(int k=0;k<i;k++)
    743 		p=tmp[n-d*k]*a[i+j+k]%mod,(a[i+j+k]=a[j+k]+mod-p)>=mod&&(a[i+j+k]-=mod),(a[j+k]+=p)>=mod&&(a[j+k]-=mod);
    744 	else for(int i=1,d=n>>1;d;i<<=1,d>>=1)for(int j=0;j<n;j+=i<<1)for(int k=0;k<i;k++)
    745 		p=tmp[d*k]*a[i+j+k]%mod,(a[i+j+k]=a[j+k]+mod-p)>=mod&&(a[i+j+k]-=mod),(a[j+k]+=p)>=mod&&(a[j+k]-=mod);
    746 	if(typ)for(int i=0;i<n;i++)a[i]=invn*a[i]%mod;
    747 }
    748 void getinv(int n,int a[],int b[]){
    749 	static int tmp[131072];
    750 	memset(b,0,sizeof(int)*(n<<1));
    751 	b[0]=ksm(a[0],mod-2);
    752 	for(int i=1;i<n;i<<=1){
    753 		init(i<<2);
    754 		memset(tmp,0,sizeof(int)*(i<<2));
    755 		memcpy(tmp,a,sizeof(int)*(i<<1));
    756 		ntt(tmp,i<<2,0);
    757 		ntt(b,i<<2,0);
    758 		for(int j=0;j<i<<2;j++)b[j]=(1ull*(mod-tmp[j])*b[j]%mod+2)*b[j]%mod;
    759 		ntt(b,i<<2,1);
    760 		memset(b+(i<<1),0,sizeof(int)*(i<<1));
    761 	}
    762 }
    763 
    764 int n,m,a[131072],b[131072],d0[131072],d1[131072],len,ans;
    765 
    766 void work(int v){
    767 	if(v==1){
    768 		for(int i=0;i<len;i++)a[i]=1;
    769 		ans=1;
    770 		return;
    771 	}
    772 	work(v>>1);
    773 	memset(d0,0,sizeof(int)*(len<<1));
    774 	memset(d1,0,sizeof(int)*(len<<1));
    775 	for(int i=0;i<len;i++)(i&1?d1:d0)[i]=a[i];
    776 	if(v&1)++d1[1]==mod&&(d1[1]=0);
    777 	memset(a,0,sizeof(int)*(len<<1));
    778 	for(int i=0;i<len;i++)a[i]=d1[i]?mod-d1[i]:0;
    779 	++a[0]==mod&&(a[0]=0);
    780 	getinv(len,a,b);
    781 	if(v==m||!(n&1)){
    782 		int Ans=0;
    783 		for(int i=1;i<=n;i+=2)
    784 			Ans=(1ull*d1[i]*b[n-i]%mod*i+Ans)%mod;
    785 		if(!(n&1))ans=(2ull*ans+Ans)%mod;
    786 		else ans=Ans;
    787 		if(v==m)return;
    788 	}
    789 	init(len<<1);
    790 	ntt(d0,len<<1,0);
    791 	for(int i=0;i<len<<1;i++)d0[i]=1ull*d0[i]*d0[i]%mod;
    792 	ntt(d0,len<<1,1);
    793 	memset(d0+len,0,sizeof(int)*len);
    794 	ntt(d0,len<<1,0);
    795 	ntt(b,len<<1,0);
    796 	for(int i=0;i<len<<1;i++)a[i]=1ull*d0[i]*b[i]%mod;
    797 	ntt(a,len<<1,1);
    798 	for(int i=1;i<len;i+=2)(a[i]+=d1[i])>=mod&&(a[i]-=mod);
    799 	if(v&1)a[1]?a[1]--:a[1]=mod-1;
    800 }
    801 
    802 int main(){
    803 	scanf("%d%d",&n,&m);
    804 	len=n<<1;
    805 	while(len^len&-len)len^=len&-len;
    806 	work(m);
    807 	printf("%d\n",ans);
    808 }
    809 ```
    810 
    811 **UPD:** Chinese editorial can be found [here](https://www.luogu.com.cn/blog/269442/cf745).