1580.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  424 425 Otherwise, like the case below, we can choose path (1 -> a -> t) and path (1 -> b -> s). 426 427  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).