2116.md (41361B)
1 Source: https://codeforces.com/blog/entry/143418 2 3 You could tell people didn't seem to like the match very much. I'm sorry I screwed up again ¯\_(ツ)_/¯ 4 5 If you're interested, I'd like to share some thoughts I have about this contest. 6 7 **sad story** 8 9 This time I've been trying my best to make the problems use more varied algorithms instead of just dp problems, but sadly [2115C - Gellyfish and Eternal Violet](/contest/2115/problem/C "Codeforces Round 1028 (Div. 1)") was much harder than expected. 10 11 But it seems like people are complaining more about the narrow time limit, centered on [2116C - Gellyfish and Flaming Peony](/contest/2116/problem/C "Codeforces Round 1028 (Div. 2)") and [2115C - Gellyfish and Eternal Violet](/contest/2115/problem/C "Codeforces Round 1028 (Div. 1)"). 12 13 No one realized this before the contest, because none of the tester's code is get TLE except the wrong time complexity. 14 15 I actually don't see a problem with the Time Limit of [2116C - Gellyfish and Flaming Peony](/contest/2116/problem/C "Codeforces Round 1028 (Div. 2)"). Some of you may be puzzled, but let me try to explain this: 16 17 * The intended solution is $O(\sum n \max(a) + \max(a)^2)$ and does not contain $\log \max(a)$. Computing $\gcd(x, y)$ is not $O(1)$, if you don't preprocess, then it's not unusual to actually get a TLE. 18 * I believe the vast majority of people who get TLE do so for this reason, and you might argue that it's actually hard to tell whether it's the constant that's too large or the time complexity that's wrong. I would say that normally, if someone expects $O(n^2 \log n)$ to pass, then the questioner would set it to $n \leq 2000$ instead of $n \leq 5000$. 19 * I'll admit that $n, a_i \leq 2000$ would have been better, "Happy AC" isn't a bad thing, this is not Div.1 F and we shouldn't limit complexity to such a narrow range. I'm ignoring the fact that most people who get a TLE will assume that the constant is too large, and thus not even think about the large amount of time wasted from optimizing the complexity. 20 * If someone's solution is $O(\sum n \max(a) + \max(a)^2)$ and it gets TLE, I really don't know why. The speed performance of array accesses on Codeforces is very strange (also happens on [2115C - Gellyfish and Eternal Violet](/contest/2115/problem/C "Codeforces Round 1028 (Div. 1)")), the vast majority of $O(\sum n \max(a) + \max(a)^2)$ code which gets TLE performs quite well locally, I didn't realize this until after the contest. It's extremely hard for this to happen, I've tried various modifications to std, including swapping the order of the two dimensions of the array and the enumerations i, j, and none of them have gotten a TLE. it's only possible to get a TLE if your code is in an extremely unlucky situation, otherwise going beyond $1$ second is almost impossible if you are using C++. 21 22 For [2115C - Gellyfish and Eternal Violet](/contest/2115/problem/C "Codeforces Round 1028 (Div. 1)"), I'll admit it was a huge mistake: 23 24 * A $O(m^2 h)$ code is so fast that it takes less than $5$ seconds even at today's ranges, It runs so fast that I ignored the constants in order to prevent it from passing. The speed of std and testers' codes gave me too much confidence. (Although it was ultimately discovered that some testers' codes did not encounter the worst-case scenario) I should indeed guarantee $\sum n \leq 50 $ instead of $\sum n \leq 100$. 25 * Now I deeply realize that for all but the last few problems, the probability of unintended solutions passing due to extreme constant optimization is far less than the probability of intended solutions receiving TLE. Very few people master instruction sets and extreme constant optimization techniques, and their skill level is usually high enough to handle these problems. The effort required to pass these problems through extreme constant optimization often outweighs simply reconsidering the correct time complexity. I hope the failure of this contest will make future problem authors aware of this issue. 26 * In fact, the original constraints for [2115C - Gellyfish and Eternal Violet](/contest/2115/problem/C "Codeforces Round 1028 (Div. 1)") were $n \leq 100, m \leq 2000, h_i \leq 100$ which would have prevented the current situation. If someone passes your problem through extreme constant optimization, think carefully based on the problem's difficulty—whether you should increase the constraints or just give everyone a "Happy AC." 27 28 In any case, it's all over now. Though this wasn't a perfect ending, 'Life goes on.' Hope Codeforces contests will keep improving, and wish those reading this better results in future competitions. 29 30 #### [2116A - Gellyfish and Tricolor Pansy](/contest/2116/problem/A "Codeforces Round 1028 (Div. 2)") 31 32 Idea: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Solution: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Prepared by: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") 33 34 **Hint 1** 35 36 Please think carefully about what happens after the death of either knight. 37 38 **Solution** 39 40 While a player who goes to $0$ HP will lose the game outright, when a player's knight dies, she loses the ability to attack; then in future rounds, she can only be attacked by her opponent and thus lose the game. 41 42 Thus it can be found that the player herself is as important as her knights, and she loses the game when either of them becomes $0$ HP. 43 44 Therefore, the optimal strategy for both of them is to attack the one with lower HP. So when $\min(a, c)$ is greater than or equal to $\min(b, d)$, Gellyfish wins, otherwise Flower wins. 45 46 Time complexity: $O(1)$ per test case. 47 48 Memory complexity: $O(1)$ per test case. 49 50 **Code** 51 52 ``` 53 #include<bits/stdc++.h> 54 55 using namespace std; 56 57 inline void solve(){ 58 int a = 0, b = 0, c = 0, d = 0; 59 scanf("%d %d %d %d", &a, &b, &c, &d); 60 if(min(a, c) >= min(b, d)) printf("Gellyfish\n"); 61 else printf("Flower\n"); 62 } 63 64 int T = 0; 65 66 int main(){ 67 scanf("%d", &T); 68 for(int i = 0 ; i < T ; i ++) solve(); 69 return 0; 70 } 71 ``` 72 73 #### [2116B - Gellyfish and Baby's Breath](/contest/2116/problem/B "Codeforces Round 1028 (Div. 2)") 74 75 Idea: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Solution: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Prepared by: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") 76 77 **Hint 1** 78 79 How to quickly compare $2^a + 2^b$ and $2^c + 2^d$ for given integers $a, b, c, d$ is the key. 80 81 **Hint 2** 82 83 We are given two permutations of $p$ and $q$, which means that each element will appear only once in both $p$ and $q$, respectively. What's the point of this? 84 85 **Solution** 86 87 For given integers $a, b, c, d$ , if we want to compare $2^a+2^b$ and $2^c+2^d$, we actually need to compare $\max(a, b)$ with $\max(c, d)$ first, and $\min(a, b)$ with $\min(c, d)$ second. This is due to $2^k = 2^{k-1} + 2^{k-1}$; when $\max(c, d) \lt \max(a, b)$, $2^c + 2^d \leq 2 \times 2^{\max(c, d)} \leq 2^{\max(a, b)}$, and it's symmetric for $\max(a, b) \lt \max(c, d)$. 88 89 So for all $i$, we only need to find $j = \arg \max\limits_{1 \leq l \leq i} p_l, k = \arg \max\limits_{1 \leq l \leq i} q_l$, then $r_i = \max(2^{p_j} + 2^{q_{i-j}}, 2^{p_{i-k}} + 2^{q_k})$. This is easily done in $O(n)$ time. 90 91 Time complexity: $O(n)$ per test case. 92 93 Memory complexity: $O(n)$ per test case. 94 95 **Code** 96 97 ``` 98 #include<bits/stdc++.h> 99 100 using namespace std; 101 102 const int N = 1e5 + 5, Mod = 998244353; 103 int n = 0, s[N] = {}, p[N] = {}, q[N] = {}, r[N] = {}; 104 105 inline void solve(){ 106 scanf("%d", &n); 107 for(int i = 0 ; i < n ; i ++) scanf("%d", &p[i]); 108 for(int i = 0 ; i < n ; i ++) scanf("%d", &q[i]); 109 for(int i = 0, j = 0, k = 0 ; k < n ; k ++){ 110 if(p[k] > p[i]) i = k; if(q[k] > q[j]) j = k; 111 if(p[i] != q[j]){ 112 if(p[i] > q[j]) printf("%d ", (s[p[i]] + s[q[k - i]]) % Mod); 113 else printf("%d ", (s[q[j]] + s[p[k - j]]) % Mod); 114 } 115 else printf("%d ", (s[p[i]] + s[max(q[k - i], p[k - j])]) % Mod); 116 } 117 printf("\n"); 118 } 119 120 int T = 0; 121 122 int main(){ 123 s[0] = 1; for(int i = 1 ; i < N ; i ++) s[i] = s[i - 1] * 2 % Mod; 124 scanf("%d", &T); 125 while(T --) solve(); 126 return 0; 127 } 128 ``` 129 130 #### [2115A - Gellyfish and Flaming Peony](/contest/2115/problem/A "Codeforces Round 1028 (Div. 1)") 131 132 Idea: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Solution: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Prepared by: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") 133 134 **Hint 1** 135 136 Try to think about why Gellyfish can always achieve her goal, and ultimately what all the elements will turn into. 137 138 **Hint 2** 139 140 When you've figured out **Hint 1**, try using dynamic programming to reach your goal. 141 142 **Solution** 143 144 Let $g = \gcd(a_1, a_2, \dots, a_n)$, It can be shown that eventually all elements become $g$. 145 146 Consider the assumption that eventually all numbers are $x$. Then for all $i$, there is $x\ |\ a_i$; this is because as $a_i := \gcd(a_i, a_j)$, the new $a_i$ value will only be a factor of the original. It further follows that $x\ |\ g$. 147 148 Further analysis reveals that $x$ cannot be less than $g$, no matter how it is manipulated. Thus we have $x = g$. 149 150 Next we consider that after a certain number of operations, if there exists some $a_k$ equal to $g$. In the next operations, for each element $a_i$ that is not equal to $g$, we simply choose $j=k$ and then make $a_i := \gcd(a_i, a_k)$. After this, all elements will become $g$. 151 152 If $g$ is initially in $a$, then the problem is simple; we just need to count the number of elements in $a$ that are not equal to $g$. 153 154 But if the initial $g$ is not in $a$, we are actually trying to make an element equal to $g$ by minimizing the number of operations. 155 156 This is not difficult to achieve through dynamic programming, using $f_x$ to indicate that it takes at least a few operations to make an element equal to $x$. 157 158 The transition is simple, just enumerate $x$ from largest to smallest, and then for all $i$, use $f_{x}+1$ to update $f_{\gcd(x, a_i)}$. 159 160 But computing $\gcd(x, y)$ is $O(\log x)$, a direct transition takes $O(n \max(a) \log \max(a))$ time. So we need to preprocess this. Let $h_{x, y} = \gcd(x, y)$, then there is obviously $h_{x, y} = h_{y, x \bmod y}$. Before all test cases, $h$ can be preprocessed in $O(\max(a)^2)$ time complexity. 161 162 Time complexity: $O(n \max(a))$ per test case and $O(\max(a)^2)$ for preprocessing. 163 164 Memory complexity: $O(n+\max(a))$ per test case and $O(\max(a)^2)$ for preprocessing. 165 166 **Bonus** 167 168 Try to solve $n, a_i \leq 2 \times 10^5$ with only one test case. 169 170 **Code** 171 172 ``` 173 #include<bits/stdc++.h> 174 175 using namespace std; 176 177 const int N = 5000 + 5; 178 179 inline void checkmax(int &x, int y){ 180 if(y > x) x = y; 181 } 182 183 inline void checkmin(int &x, int y){ 184 if(y < x) x = y; 185 } 186 187 int n = 0, m = 0, k = 0, a[N] = {}, f[N] = {}; 188 int g[N][N] = {}, ans = 0; 189 190 inline void solve(){ 191 scanf("%d", &n); m = k = 0; 192 for(int i = 1 ; i <= n ; i ++){ 193 scanf("%d", &a[i]); 194 k = g[k][a[i]]; 195 } 196 memset(f, 0x3f, sizeof(f)); 197 for(int i = 1 ; i <= n ; i ++) a[i] /= k, checkmax(m, a[i]), f[a[i]] = 0; 198 for(int x = m ; x >= 1 ; x --) for(int i = 1 ; i <= n ; i ++){ 199 int y = a[i]; 200 checkmin(f[g[x][y]], f[x] + 1); 201 } 202 ans = max(f[1] - 1, 0); 203 for(int i = 1 ; i <= n ; i ++) if(a[i] > 1) ans ++; 204 printf("%d\n", ans); 205 } 206 207 int T = 0; 208 209 int main(){ 210 for(int x = 0 ; x < N ; x ++) g[x][0] = g[0][x] = g[x][x] = x; 211 for(int x = 1 ; x < N ; x ++) for(int y = 1 ; y < x ; y ++) g[x][y] = g[y][x] = g[y][x % y]; 212 scanf("%d", &T); 213 while(T --) solve(); 214 return 0; 215 } 216 ``` 217 218 #### [2115B - Gellyfish and Camellia Japonica](/contest/2115/problem/B "Codeforces Round 1028 (Div. 1)") 219 220 Idea: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Solution: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Prepared by: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") 221 222 **Hint 1** 223 224 Try working backwards from the final sequence, to the initial. 225 226 **Hint 2** 227 228 If you're confused about **Hint 1**, it's probably because the result isn't unique each time. Think carefully about whether you can just take the "tightest" result possible 229 230 **Solution** 231 232 Let's think of the problem in another way, if we only require that for all $i$, the final value of $c_i$ is greater than or equal to $b_i$, what will be the limitations for all $a_i$? 233 234 It is possible to prove that the restricted form exists as a sequence $l$. It is sufficient that $a_i \geq l_i$ for all $i$. 235 236 Next we try to illustrate this thing, we need to work backward from the last operation and observe the restrictions on $c$ in each step. After the last operation, we have $c_i \geq b_i$, which means $l = b$. 237 238 Consider an operation that replaces $c_z$ with $\min(c_x, c_y)$. If for a post-operation restriction of $l$, can we recover the pre-operation restriction $l'$? Let us think as follows: 239 240 * It is not difficult to find that for $i \notin {x, y, z}$, $l'_i = l_i$. 241 * $l'_z = 0$, because the $c_z$ before the operation is overwritten, it will not actually have any restrictions. 242 * $l'_x = \max(l_x, l_z), l'_y = \max(l_y, l_z)$. Since the new $c_z$ is the original $\min(c_x, c_y)$, it can be found that for the original $c_x$, we have $c_x \geq \min(c_x, c_y) = c_z \geq l_z$, while for $y$ is symmetric. 243 244 We have thus proved that, according to the eventually obtained $l$, $a_i \geq l_i$ for all $i$ is a sufficient condition to eventually make all $c_i \geq b_i$ for all $i$ . 245 246 And ultimately all $c_i = b_i$, thus for all $i$, $a_i \geq l_i$ is necessary. In fact, we could just take $a=l$ and do all the operations sequentially to see if we end up with $c=b$. This is because as $a$ decreases, eventually $c$ decreases as well, and by the $l$ guarantee there is always $c_i \geq b_i$, so in effect we are trying to minimize all of $c$, and then minimizing all of $a$ is clearly an optimal decision. 247 248 Time complexity: $O(n + q)$ per test case. 249 250 Memory complexity: $O(n + q)$ per test case. 251 252 **Code** 253 254 ``` 255 #include<bits/stdc++.h> 256 257 using namespace std; 258 259 const int N = 3e5 + 5; 260 int n = 0, q = 0, a[N] = {}, b[N] = {}, c[N] = {}; 261 int x[N] = {}, y[N] = {}, z[N] = {}; 262 263 inline void init(){ 264 for(int i = 1 ; i <= n ; i ++) a[i] = b[i] = c[i] = 0; 265 for(int i = 1 ; i <= q ; i ++) x[i] = y[i] = z[i] = 0; 266 n = q = 0; 267 } 268 269 inline void solve(){ 270 cin >> n >> q; 271 for(int i = 1 ; i <= n ; i ++){ 272 cin >> b[i]; 273 c[i] = b[i]; 274 } 275 for(int i = 1 ; i <= q ; i ++) cin >> x[i] >> y[i] >> z[i]; 276 for(int i = q ; i >= 1 ; i --){ 277 int v = c[z[i]]; c[z[i]] = 0; 278 c[x[i]] = max(c[x[i]], v), c[y[i]] = max(c[y[i]], v); 279 } 280 for(int i = 1 ; i <= n ; i ++) a[i] = c[i]; 281 for(int i = 1 ; i <= q ; i ++) c[z[i]] = min(c[x[i]], c[y[i]]); 282 for(int i = 1 ; i <= n ; i ++) if(b[i] != c[i]){ 283 cout << "-1\n"; 284 return; 285 } 286 for(int i = 1 ; i <= n ; i ++) cout << a[i] << ' '; 287 cout << '\n'; 288 } 289 290 int T = 0; 291 292 int main(){ 293 ios :: sync_with_stdio(0); 294 cin.tie(0), cout.tie(0); 295 cin >> T; 296 for(int i = 0 ; i < T ; i ++) init(), solve(); 297 298 return 0; 299 } 300 ``` 301 302 #### [2115C - Gellyfish and Eternal Violet](/contest/2115/problem/C "Codeforces Round 1028 (Div. 1)") 303 304 Idea: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Solution: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Prepared by: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") 305 306 **Hint 1** 307 308 Try to find an $O(nm h^2)$ solution using dynamic programming. 309 310 **Hint 2** 311 312 Re-examining Gellyfish's strategy, there are definitely situations where she chooses to carry out an attack. Can we divide the $m$ rounds into two phases by some nature? 313 314 **Solution** 315 316 Considering all current monsters, if the lowest HP of the monsters is $l$, Gellyfish can only make at most $l-1$ "ranged" attacks. 317 318 So for each monster, if its HP is $h_i$, then it must be subject to at least $h_i - l$ "pointing" attacks. Further, we can see that we only care about $l$ and $\sum\limits_{i=1}^n (h_i - l)$. 319 320 Consider directly using $f_{i, l, x}$ to indicate that there are still $i$ rounds to go, the lowest HP of the monsters is $l$, and $x = \sum\limits_{i=1}^n (h_i - l)$, the probability that Gellyfish will reach her goal. This solves the problem within $O(nmh^2)$, but that's not enough. 321 322 Consider the initial HP of all monsters, let $l = \min\limits_{i=1}^n h_i, s = \sum\limits_{i=1}^n (h_i - l)$. For the first $s$ times the sword doesn't shine, Gellyfish will obviously launch an attack. 323 324 So we using $g_{i, j}$ to indicate the probability that the sword did not shine exactly $j$ times in the first $i$ rounds and the last time the sword did not shine. We then enumerate the $s$-th time that the sword didn't shine. We can divide the problem into two parts. The first half can be solved using $g$, while the second half can be solved using $f$, We just need to merge the results of the two parts, which is not difficult. 325 326 When we use f to solve the second part, it is easy to see that initially all monsters have the same HP, and each "pointing" attack can directly attacks the monster with the highest HP, which doesn't make the answer worse. So we have $h_i - l \leq 1$ for any time, and the range of $x$ that we actually need is compressed to $[0, n)$. 327 328 Time complexity: $O(nmh)$ per test case. 329 330 Memory complexity: $O(nmh)$ per test case. 331 332 **Code** 333 334 ``` 335 #include<bits/stdc++.h> 336 337 using namespace std; 338 339 const int N = 22, K = 4000 + 5, M = 400 + 5, Inf = 0x3f3f3f3f; 340 341 inline void checkmin(double &x, double y){ 342 if(y < x) x = y; 343 } 344 345 int n = 0, m = 0, s = 0, k = 0, p0 = 0, h[N] = {}; 346 double p = 0, f[K][K] = {}, g[K][N][M] = {}, ans = 0; 347 348 inline void init(){ 349 for(int i = 0 ; i <= k ; i ++){ 350 for(int c = 0 ; c < n ; c ++) for(int x = 0 ; x <= m ; x ++) g[i][c][x] = 0; 351 for(int x = 0 ; x <= s ; x ++) f[i][x] = 0; 352 } 353 m = Inf, s = 0, ans = 0; 354 } 355 356 inline void solve(){ 357 scanf("%d %d %d", &n, &k, &p0); 358 p = 1.0 * p0 / 100; 359 for(int i = 1 ; i <= n ; i ++){ 360 scanf("%d", &h[i]); h[i] --; 361 m = min(m, h[i]); 362 } 363 for(int i = 1 ; i <= n ; i ++) s += h[i] - m; 364 if(s > k){ 365 printf("0.000000\n"); 366 return; 367 } 368 g[0][0][0] = 1; 369 for(int i = 1 ; i <= k ; i ++){ 370 g[i][0][0] = 1; 371 for(int x = 1 ; x <= m ; x ++) g[i][0][x] = g[i - 1][0][x - 1] * p + max(g[i - 1][0][x], g[i - 1][n - 1][x - 1]) * (1 - p); 372 for(int c = 1 ; c < n ; c ++){ 373 g[i][c][0] = g[i - 1][c][0] * p + g[i - 1][c - 1][0] * (1 - p); 374 for(int x = 1 ; x <= m ; x ++) g[i][c][x] = g[i - 1][c][x - 1] * p + g[i - 1][c - 1][x] * (1 - p); 375 } 376 } 377 f[0][0] = 1; 378 for(int i = 0 ; i < k ; i ++) for(int x = 0 ; x < s ; x ++){ 379 f[i + 1][x] += f[i][x] * p; 380 f[i + 1][x + 1] += f[i][x] * (1 - p); 381 } 382 for(int i = s ; i <= k ; i ++){ 383 double r = 0; 384 for(int x = 0 ; x <= min(i - s, m) ; x ++) r = max(r, g[k - i][0][m - x]); 385 ans += r * f[i][s]; 386 } 387 printf("%.6lf\n", ans); 388 } 389 390 int T = 0; 391 392 int main(){ 393 scanf("%d", &T); 394 while(T --) init(), solve(); 395 return 0; 396 } 397 ``` 398 399 #### [2115D - Gellyfish and Forget-Me-Not](/contest/2115/problem/D "Codeforces Round 1028 (Div. 1)") 400 401 Idea: [MagicalFlower](/profile/MagicalFlower "International Grandmaster MagicalFlower") Solution: [MagicalFlower](/profile/MagicalFlower "International Grandmaster MagicalFlower") Prepared by: [MagicalFlower](/profile/MagicalFlower "International Grandmaster MagicalFlower") 402 403 **Hint 1** 404 405 Consider if $c$ consists only of $0$, this problem turned out to be another classic problem. So you need at least something that you know what it is. 406 407 **Hint 2** 408 409 "linear basis" is the answer to **Hint 1**. Please try to understand this: all addition operations are interpreted as XOR operations. 410 411 **Solution** 412 413 We can assume that the initial value of $x$ is $\sum a_i$. In each step, we can choose to add $c_i = a_i + b_i$ to $x$, or do nothing. Each suffix of the sequence can be seen as a subproblem, so we prove inductively that the answer, as a function $f(x)$ of the initial value of $x$, is an affine transformation, i.e., $f(x) = Ax + b$. 414 415 When $n = 0$, this is trivial: $f(x) = x$. 416 417 When $n \gt 1$, we can choose to add $c_i$ to $x$ or not. Let $f(x)$ denote the answer function from the second operation onward. The two possible outcomes correspond to: 418 419 * Not choosing $c_i$: result is $f(x)$ 420 * Choosing $c_i$: result is $f(x + c_i) = f(x) + f(c_i) + b$. 421 422 Although we don't know the exact value of $x$, $f(c_i) + b$ is a constant. Suppose the highest set bit in the binary representation of $f(c_i) + b$ is at position $k$. Then, the decision of whether to apply this operation depends only on: 423 424 1. Whether we want to maximize or minimize the final answer 425 2. Whether the $k$-th bit of $f(x)$ is $0$ or $1$ 426 427 It is easy to observe that the new function $g(x)$ (before this decision) remains a affine transformation, satisfying $g(x) = g(x + c_i)$. 428 429 Based on the above process, we can represent the answer function $f(x)$ using a orthogonal basis. Each element in the orthogonal basis represents a vector in the null space of $A$. Additionally, we keep a tag for each vector, indicating whether it is used to increase or decrease the value of $x$. 430 431 In each iteration, we try to insert $c_i$ into the linear basis, and associate it with a tag depending on the index $i$. 432 433 Time complexity: $O(n \log \max(a, b, x))$ per test case. 434 435 Memory complexity: $O(n + \log \max(a, b, x))$ per test case. 436 437 **Code** 438 439 ``` 440 #include <bits/stdc++.h> 441 using i64 = long long; 442 constexpr int L = 60; 443 int main() { 444 std::ios::sync_with_stdio(false), std::cin.tie(0); 445 int T; 446 for(std::cin >> T; T; T --) { 447 int n; 448 std::cin >> n; 449 std::vector<i64> a(n), b(n); 450 std::string str; 451 i64 all = 0; 452 for(auto &x : a) std::cin >> x, all ^= x; 453 for(int i = 0; i < n; i ++) { 454 std::cin >> b[i]; 455 b[i] ^= a[i]; 456 } 457 std::cin >> str; 458 std::vector<i64> bas(L); 459 std::vector<int> bel(L, -1); 460 i64 ans = 0; 461 for(int i = n - 1; i >= 0; i --) { 462 i64 x = b[i], col = str[i] - '0'; 463 for(int i = L - 1; i >= 0; i --) if(x >> i & 1) { 464 if(bas[i]) { 465 x ^= bas[i]; 466 } else { 467 for(int j = i - 1; j >= 0; j --) if(x >> j & 1) { 468 x ^= bas[j]; 469 } 470 bas[i] = x; 471 for(int j = L - 1; j > i; j --) if(bas[j] >> i & 1){ 472 bas[j] ^= bas[i]; 473 } 474 bel[i] = col; 475 break; 476 } 477 } 478 } 479 480 for(int i = L - 1; i >= 0; i --) if(all >> i & 1) { 481 all ^= bas[i]; 482 } 483 for(int i = 0; i < L; i ++) if(bel[i] == 1) ans ^= bas[i]; 484 std::cout << (all ^ ans) << '\n'; 485 } 486 487 return 0; 488 } 489 ``` 490 491 #### [2115E - Gellyfish and Mayflower](/contest/2115/problem/E "Codeforces Round 1028 (Div. 1)") 492 493 Idea: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Solution: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Prepared by: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") 494 495 **Hint 1** 496 497 There is an easy way to solve the problem in $O(m \max(r) + q)$ time complexity. Thus for cases with small $r$, we can easily solve them, but what about cases with large $r$? 498 499 **Hint 2** 500 501 There is a classic but mistaken greed where we only take the item with the largest $\frac w c$. This is obviously wrong, but **Hint 1** lets us rule out the case where r is small; is there an efficient algorithm that can fix this greed for larger $r$? 502 503 **Solution** 504 505 Let $s$ be any path from vertex $1$ to vertex $p$, the vertices that pass through in turn are $s_1, s_2, \dots, s_k$. 506 507 Let $z$ be the vertex in $s$ with the largest $\frac {w} {c}$, and $C = c_z, W = w_z$. 508 509 Let's call your cards you don't get from vertex $z$ as special cards. 510 511 **Lemma1.** There exists an optimal solution such that the number of special cards does not exceed $C$. 512 513 **Proof.** Let $c'_1, c'_2, \dots, c'_{k'}$ be the cost of the special cards, and $p'_i = \sum_{j=1}^i {c'}_j$. If there exists $0 \leq l \lt r \leq k',\ p'_l \equiv p'_r \bmod C$, we will get that $\sum_{i=l'+1}^{r'} p_i \equiv 0 \bmod C$. Then we can replaces these cards with $\frac {\sum_{i=l'+1}^{r'} p_i} C$ cards from vertex $z$, the answer won't be worse. Since there are only $C+1$ values of $x \bmod C$ for all non-negative integers $x$, there are no more than $C$ special cards. 514 515 So it's not hard to find the total cost of special cards won't exceed $\max(c)^2$. 516 517 Now we can use dynamic programming to solve this problem: 518 519 * $dp(u, v, x, 0/1)$ means we are current at vertex $u$, the vertex on the path with the largest $\frac {w} {c}$ is $v$, the total cost of the cards is $x$, we have reached the vertex $v$ or not, the maximum sum of the power of the cards. 520 521 Since the remainder will be filled by cards from $v$, We just need to find the value of $dp(u, v, x)$ that satisfies $1 \leq x \leq \max(c)^2$. 522 523 But unfortunately, the time complexity of the algorithm is $O(mn\max(c)^2)$. It's not fast enough. 524 525 At this point you'll find that solving the problem directly becomes incredibly tricky, so we'll try to split it into two problems. 526 527 We first consider the following problem: whether there is a better solution when $r$ is sufficiently large? 528 529 We need to broaden the problem, so we try to be able to buy a negative number of cards with the largest $\frac {w} {c}$. 530 531 Doing so would make the answer larger, but when $r$ is large enough, the answer won't change. Because according to **Lemma1**, if the total cost of special cards exceed $\max(c)^2$, there will be a solution that's at least not worse. 532 533 Thus when $r \gt \max(c)^2$, that's the answer of the problem. And we can use another dynamic programming to solve this problem: 534 535 * $g(u, v, x, 0/1)$ means we are current at vertex $u$, the vertex on the path with the largest $\frac {w} {c}$ is $v$, the total cost of the cards is $x$, we have reached the vertex $v$ or not, the maximum sum of the power of the cards. 536 537 But unlike the original, when $x$ is equal to or greater than $c_v$, we remove several cards from vertex $v$ to make $0 \leq x \lt c_v$. 538 539 The time complexity becomes $O(mn \max(c))$, now it's fast enough. 540 541 For each query, we can just enumerate $v$ in $O(n)$ time complexity. 542 543 As for $r \leq max(c)^2$? It's an easy problem: 544 545 * $f(u, x)$ means we are current at vertex $u$, the total cost of the cards is $x$, the maximum sum of the power of the cards. 546 547 The time complexity is $O(m \max(c)^2)$. 548 549 For each query, we can get the answer directly from $f$ in $O(1)$ time complexity. 550 551 Over all, we have solved the problem. 552 553 Time complexity: $O(mn \max(c) + m \max(c)^2 + qn)$ 554 555 Memory complexity: $O(n^2 \max(c) + n \max(c)^2)$ 556 557 **Code** 558 559 ``` 560 #include<bits/stdc++.h> 561 562 using namespace std; 563 typedef long long ll; 564 565 const ll N = 200 + 5, Inf = 0xcfcfcfcfcfcfcfcf; 566 567 inline ll sqr(ll x){ 568 return x * x; 569 } 570 571 inline ll gcd(ll x, ll y){ 572 if(y) return gcd(y, x % y); 573 else return x; 574 } 575 576 inline void checkmax(ll &x, ll y){ 577 if(y > x) x = y; 578 } 579 580 ll n = 0, m = 0, magic = 0, w[N] = {}, c[N] = {}; 581 ll f[N][N * N] = {}, g[N][N][N][2] = {}; 582 vector<vector<ll> > G(N); 583 584 inline void main_min(){ 585 memset(f, 0xcf, sizeof(f)); 586 for(ll x = 0 ; x <= magic ; x ++) f[1][x] = 0; 587 for(ll u = 1 ; u <= n ; u ++){ 588 for(ll x = 0 ; x + c[u] <= magic ; x ++) checkmax(f[u][x + c[u]], f[u][x] + w[u]); 589 for(ll v : G[u]) for(ll x = 0 ; x <= magic ; x ++) checkmax(f[v][x], f[u][x]); 590 } 591 } 592 593 inline void solve_max(ll i){ 594 ll a = c[i], b = w[i]; 595 for(ll x = 0 ; x < a ; x ++) g[i][1][x][0] = 0; 596 for(ll u = 1 ; u <= n ; u ++){ 597 if(u == i) for(ll x = 0 ; x < a ; x ++) checkmax(g[i][u][x][1], g[i][u][x][0]); 598 else if(w[u] * a > c[u] * b) memset(g[i][u], 0xcf, sizeof(g[i][u])); 599 for(ll s = 0, k = gcd(c[u], a) ; s < k ; s ++) for(ll x = s, t = 0 ; t < 2 * (a / k) ; x = (x + c[u]) % a, t ++){ 600 checkmax(g[i][u][(x + c[u]) % a][0], g[i][u][x][0] + w[u] - ((x + c[u]) / a) * b); 601 checkmax(g[i][u][(x + c[u]) % a][1], g[i][u][x][1] + w[u] - ((x + c[u]) / a) * b); 602 } 603 for(ll v : G[u]) for(ll x = 0 ; x < a ; x ++){ 604 checkmax(g[i][v][x][0], g[i][u][x][0]); 605 checkmax(g[i][v][x][1], g[i][u][x][1]); 606 } 607 } 608 } 609 610 inline void main_max(){ 611 memset(g, 0xcf, sizeof(g)); 612 for(ll i = 1 ; i <= n ; i ++) solve_max(i); 613 } 614 615 int main(){ 616 scanf("%lld %lld", &n, &m); 617 for(ll i = 1 ; i <= n ; i ++){ 618 scanf("%lld %lld", &c[i], &w[i]); 619 magic = max(magic, sqr(c[i])); 620 } 621 for(ll i = 1, u = 0, v = 0 ; i <= m ; i ++){ 622 scanf("%lld %lld", &u, &v); 623 G[u].push_back(v); 624 } 625 main_min(), main_max(); 626 ll q = 0, p = 0, r = 0; 627 scanf("%lld", &q); 628 while(q --){ 629 scanf("%lld %lld", &p, &r); 630 if(r <= magic) printf("%lld\n", f[p][r]); 631 else{ 632 ll ans = Inf; 633 for(ll i = 1 ; i <= n ; i ++){ 634 ll a = c[i], b = w[i]; 635 checkmax(ans, g[i][p][r % a][1] + (r / a) * b); 636 } 637 printf("%lld\n", ans); 638 } 639 } 640 return 0; 641 } 642 ``` 643 644 #### [2115F1 - Gellyfish and Lycoris Radiata (Easy Version)](/contest/2115/problem/F1 "Codeforces Round 1028 (Div. 1)") 645 646 Idea: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") User Solution: [JoesSR](/profile/JoesSR "Legendary Grandmaster JoesSR"), [zhaohaikun](/profile/zhaohaikun "International Grandmaster zhaohaikun") Prepared by: [MagicalFlower](/profile/MagicalFlower "International Grandmaster MagicalFlower") 647 648 **Solution** 649 650 We apply block decomposition to the operations, dividing every $B$ operations into a single round. Within each round, the sequence is partitioned into $O(B)$ segments. For each segment, we maintain a queue that records all elements added to that segment during the round. 651 652 * Type 1 and 2 operations can be handled directly by pushing into the appropriate segment’s queue or toggling a reversal flag. 653 * Type 3 (deletion) is handled by marking the element $x$ as deleted without immediately removing it from queues. 654 655 At the end of each round, we rebuild the sequence. Specifically, for each position in the sequence, we record which segment it belongs to, and treat the position as containing all elements currently in that segment's queue. 656 657 For queries, we process the contribution from each round one by one. In each round: 658 659 1. Identify the segment that contains position $p$. 660 2. Iterate through the queue of that segment. 661 3. For each element, if it has been marked as deleted, remove it from the front of the queue and continue; otherwise, consider it as present. 662 663 Since each element is inserted and deleted at most once per segment, and each segment has $O(1)$ amortized processing per round, the total cost per query remains efficient. 664 665 We choose $B = \sqrt{q}$, resulting in $O(\sqrt{q})$ rounds in total. The total time and space complexity is: $O((n + q)\sqrt{q})$ 666 667 **Code (by zhaohaikun)** 668 669 ``` 670 #pragma GCC optimize(2) 671 #pragma GCC optimize("Ofast") 672 #pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector") 673 #pragma GCC diagnostic error "-fwhole-program" 674 #pragma GCC diagnostic error "-fcse-skip-blocks" 675 #pragma GCC diagnostic error "-funsafe-loop-optimizations" 676 // MagicDark 677 #include <bits/stdc++.h> 678 #define debug cerr << "\33[32m[" << __LINE__ << "]\33[m " 679 #define SZ(x) ((int) x.size() - 1) 680 #define all(x) x.begin(), x.end() 681 #define ms(x, y) memset(x, y, sizeof x) 682 #define F(i, x, y) for (int i = (x); i <= (y); i++) 683 #define DF(i, x, y) for (int i = (x); i >= (y); i--) 684 using namespace std; 685 typedef long long ll; 686 typedef unsigned long long ull; 687 template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);} 688 template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);} 689 // template <typename T> T& read(T &x) { 690 // x = 0; int f = 1; char c = getchar(); 691 // for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; 692 // for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48); 693 // return x *= f; 694 // } 695 // bool be; 696 const int N = 1e5 + 1010, B = 500, B1 = N / B + 5, B2 = B + 5; 697 int n, q, ans, p[N], wp[N], tot, t[N], tl[N], tr[N]; 698 bool rev[N]; 699 bool ed[N]; 700 // bool vv[N]; 701 // struct Q1 { 702 // int tl = 1, tr; 703 // int a[B2]; 704 // bool chk() { 705 // return tl <= tr; 706 // } 707 // int front() { 708 // return a[tl]; 709 // } 710 // void pop() { 711 // tl++; 712 // } 713 // void push(int x) { 714 // a[++tr] = x; 715 // } 716 // } tq[N]; 717 // struct Q2 { 718 // int tl = 1, tr; 719 // int a[B1]; 720 // bool chk() { 721 // return tl <= tr; 722 // } 723 // int front() { 724 // return a[tl]; 725 // } 726 // void pop() { 727 // tl++; 728 // } 729 // void push(int x) { 730 // a[++tr] = x; 731 // } 732 // } vq[N]; 733 queue <int> tq[N], vq[N]; 734 vector <int> cur; 735 int qq(int x) { 736 while (tq[x].size()) { 737 if (!ed[tq[x].front()]) return tq[x].front(); 738 tq[x].pop(); 739 } 740 return 0; 741 } 742 int query(int x) { 743 int s = 0; 744 for (int i: cur) { 745 s += tr[i] - tl[i] + 1; 746 if (s >= x) { 747 int g = s - x + 1; 748 int y; 749 if (rev[i]) { 750 y = p[tl[i] + g - 1]; 751 } else { 752 y = p[tr[i] - g + 1]; 753 } 754 while (vq[y].size()) { 755 int tmp = qq(vq[y].front()); 756 if (tmp) return tmp; 757 vq[y].pop(); 758 } 759 // int tmp = qq(i); 760 // if (~tmp) return tmp; 761 return qq(i); 762 } 763 } 764 assert(false); 765 // return -1; 766 } 767 // bool ee; 768 // int cnt = 0; 769 signed main() { 770 ios::sync_with_stdio(0); // don't use puts 771 cin.tie(0), cout.tie(0); 772 // debug << abs(&ee - &be) / 1024 / 1024 << endl; 773 cin >> n >> q; 774 F(i, 1, n) p[i] = i; 775 cur.push_back(++tot); 776 tl[1] = 1, tr[1] = n; 777 F(i, 1, q) { 778 int f, x, y; cin >> f >> x >> y; 779 if (f == 3) { 780 x = (x + ans - 1) % q + 1; 781 } else { 782 x = (x + ans - 1) % n + 1; 783 } 784 y = (y + ans - 1) % n + 1; 785 // auto split = [&] (int x) { 786 // if (x > n || vv[x]) return; 787 // // vv[x] = true; 788 // for (auto []) 789 // }; 790 if (f == 1) { 791 int s = 0; 792 for (int j: cur) { 793 int w = tr[j] - tl[j] + 1; 794 s += w; 795 if (s >= x) { 796 if (s > x) { 797 tot++; 798 tq[tot] = tq[j]; 799 int g = s - x; 800 if (rev[tot] = rev[j]) { 801 tl[tot] = tl[j]; 802 tr[tot] = (tl[j] += g) - 1; 803 } else { 804 tr[tot] = tr[j]; 805 tl[tot] = (tr[j] -= g) + 1; 806 } 807 cur.insert(next(find(all(cur), j)), tot); 808 } 809 tq[j].push(i); 810 break; 811 } 812 tq[j].push(i); 813 } 814 } 815 if (f == 2) { 816 int s = 0, sz = 0; 817 for (int j: cur) { 818 sz++; 819 int w = tr[j] - tl[j] + 1; 820 s += w; 821 if (s >= x) { 822 if (s > x) { 823 tot++; 824 tq[tot] = tq[j]; 825 int g = s - x; 826 if (rev[tot] = rev[j]) { 827 tl[tot] = tl[j]; 828 tr[tot] = (tl[j] += g) - 1; 829 } else { 830 tr[tot] = tr[j]; 831 tl[tot] = (tr[j] -= g) + 1; 832 } 833 cur.insert(next(find(all(cur), j)), tot); 834 } 835 reverse(cur.begin(), cur.begin() + sz); 836 F(j, 0, sz - 1) rev[cur[j]] ^= true; 837 break; 838 } 839 } 840 } 841 if (f == 3) { 842 if (x < i) ed[x] = true; 843 } 844 cout << (ans = query(y)) << '\n'; 845 if (cur.size() >= B) { 846 int cnt = 0; 847 for (int j: cur) { 848 if (rev[j]) { 849 DF(k, tr[j], tl[j]) { 850 vq[wp[++cnt] = p[k]].push(j); 851 } 852 } else { 853 F(k, tl[j], tr[j]) { 854 vq[wp[++cnt] = p[k]].push(j); 855 } 856 } 857 } 858 F(j, 1, n) { 859 p[j] = wp[j]; 860 } 861 cur.clear(); 862 cur.push_back(++tot); 863 tl[tot] = 1, tr[tot] = n; 864 } 865 // for (int j: cur) { 866 // debug << tl[j] << " " << tr[j] << " " << rev[j] << endl; 867 // } 868 } 869 return 0; 870 } 871 ``` 872 873 #### [2115F2 - Gellyfish and Lycoris Radiata (Hard Version)](/contest/2115/problem/F2 "Codeforces Round 1028 (Div. 1)") 874 875 Idea: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Full Solution: [errorgorn](/profile/errorgorn "Legendary Grandmaster errorgorn") Prepared by: [MagicalFlower](/profile/MagicalFlower "International Grandmaster MagicalFlower") 876 877 **Solution** 878 879 We consider using leafy persistent balanced trees to maintain the sequence. At each non-leaf node, we store a set $S_u$ as a lazy tag, indicating that every set in the subtree rooted at $u$ contains $S_u$. However, since $|S_u|$ can be large, it's difficult to push down the tag efficiently. 880 881 To address this, we split each set $S_u$ into two components: 882 883 1. $T_u$: A part of $S_u$ stored directly at node $u$ 884 2. A collection of child nodes $v_{u,1}, v_{u,2}, \cdots, v_{u,k}$, each storing a subset of $S_u$ 885 886 We maintain the invariant: $S_u = T_u + \sum_{i=1}^k S_{v_{u,i}}$. 887 888 Thus, we make the balanced tree persistent. When we create a new node $u$ and initialize its children as $ls(u)$ and $rs(u)$, we add $u$ into both $v_{ls(u)}$ and $v_{rs(u)}$. During split and merge, we do not modify $T_u$, which ensures these operations still run in logarithmic time. 889 890 1. Type 1 (Insert): We split the balanced tree into two parts. Let the root of the first part be $rt$, and simply add an element into $T_{rt}$. 891 2. Type 2 (Reverse a segment): Just mark the root of the relevant subtree with a "reverse" flag. 892 3. Type 3 (Delete): Since each element $x$ appears in only one $T$, we can directly remove it from that node's $T$. 893 894 For queries, We first locate the leaf node $u$. To compute $S_u$, we need to compute all $S_{v_{u,i}}$. Due to persistence, we can guarantee: $\max(S_{v_{u,i}}) \lt \min(S_{v_{u,i+1}})$ 895 896 Thus, we can sequentially check whether each $S_{v_{u,i}}$ is empty. 897 898 We process this recursively. Every time we encounter a node $x$ with $S_x = \emptyset$ and $x$ is not part of the latest tree version, then $S_x$ will always be empty, and we can safely delete $x$. During a query, we encounter three types of nodes: 899 900 * Nodes with $|S_x| \ne 0$: We only encounter one such node per query — this is where we find the minimum value. 901 * Nodes with $|S_x| = 0$ and $x$ not in the latest tree: These nodes are deleted. Since the total number of persistent nodes is $O(q \log n)$, these nodes also appear at most that many times. 902 * Nodes with $|S_x| = 0$ and $x$ in the latest tree: These are ancestors of leaf $u$, so there are at most $O(\log n)$ of them per query. 903 904 Why can we just do $O(\log n)$ rounds of recursion? Because we replace all the nodes we pass through on the path, so the size of the subtree doesn't change from the time the node is created to the time it is removed from the tree. Furthermore, if we recurse from node $u$ to node $v$, this means that $v$ is the parent of $u$ at least at some point on the WBLT. Since the WBLT is weight-balanced, the size of the $v$ subtree is actually at least a constant multiple of the size of the $u$ subtree, and this constant greater than $1$ will be based on your WBLT. 905 906 Time complexity: $O(q \log n + n)$. 907 908 Memory complexity: $O(q \log n + n)$. 909 910 **Code** 911 912 ``` 913 #include <bits/stdc++.h> 914 constexpr int N = 3e5 + 10, S = 1.1e7, SS = 2 * S; 915 int n, q; 916 int next[SS], val[SS], cnt; 917 struct queue { 918 int head, tail; 919 void push(int x) { 920 if(head) { 921 next[tail] = ++ cnt, val[cnt] = x; tail = cnt; 922 } else { 923 head = tail = ++ cnt, val[cnt] = x; 924 } 925 assert(cnt < SS - 100); 926 } 927 void pop() {head = next[head];} 928 int front() {return val[head];} 929 bool check() {return head == tail;} 930 bool empty() {return head == 0;} 931 void clear() {head = tail = 0;} 932 }; 933 struct node { 934 int ls, rs; 935 queue fa; 936 int val, exit; 937 int size, rev; 938 }a[S]; 939 int tot; 940 int id[N]; 941 void pushup(int u) { 942 a[u].size = a[a[u].ls].size + a[a[u].rs].size; 943 } 944 void setR(int u) { 945 a[u].rev ^= 1; 946 std::swap(a[u].ls, a[u].rs); 947 } 948 void setT(int u, int v) { 949 a[u].fa.push(v); 950 } 951 void pushdown(int u) { 952 if(a[u].rev) { 953 setR(a[u].ls); 954 setR(a[u].rs); 955 a[u].rev = 0; 956 } 957 } 958 int newnode() { 959 int u = ++ tot; 960 a[u].exit = 2; 961 return u; 962 } 963 int newleaf() { 964 int u = newnode(); 965 a[u].size = 1; 966 return u; 967 } 968 int join(int x, int y) { 969 int u = newnode(); 970 a[u].ls = x, a[u].rs = y; 971 a[x].fa.push(u); 972 a[y].fa.push(u); 973 pushup(u); 974 return u; 975 } 976 auto cut(int x) { 977 pushdown(x); 978 a[x].exit = 1; 979 return std::make_pair(a[x].ls, a[x].rs); 980 } 981 int get_val(int u) { 982 if(a[u].exit == 0) return 0; 983 if(a[u].val != 0) return a[u].val; 984 if(a[u].fa.empty()) return 0; 985 int ans = 0; 986 while(1) { 987 ans = get_val(a[u].fa.front()); 988 if(ans) return ans; 989 if(a[u].fa.check()) break; 990 a[u].fa.pop(); 991 } 992 if(a[u].exit == 1) { 993 a[u].exit = 0; 994 a[u].fa.pop(); 995 a[u].fa.clear(); 996 } 997 return 0; 998 } 999 int newtag(int x) { 1000 int u = ++ tot; 1001 a[u].val = x; 1002 a[u].exit = 1; 1003 return u; 1004 } 1005 constexpr double ALPHA = 0.292; 1006 bool too_heavy(int sx, int sy) { 1007 return sy < ALPHA * (sx + sy); 1008 } 1009 int merge(int x, int y) { 1010 if(!x || !y) return x + y; 1011 if(too_heavy(a[x].size, a[y].size)) { 1012 auto [u, v] = cut(x); 1013 if(too_heavy(a[v].size + a[y].size, a[u].size)) { 1014 auto [z, w] = cut(v); 1015 return merge(merge(u, z), merge(w, y)); 1016 } else { 1017 return merge(u, merge(v, y)); 1018 } 1019 } else if(too_heavy(a[y].size, a[x].size)) { 1020 auto [u, v] = cut(y); 1021 if(too_heavy(a[u].size + a[x].size, a[v].size)) { 1022 auto [z, w] = cut(u); 1023 return merge(merge(x, z), merge(w, v)); 1024 } else { 1025 return merge(merge(x, u), v); 1026 } 1027 } else { 1028 return join(x, y); 1029 } 1030 } 1031 std::pair<int, int> split(int x, int k) { 1032 if(!x) return {0, 0}; 1033 if(!k) return {0, x}; 1034 if(k == a[x].size) return {x, 0}; 1035 auto [u, v] = cut(x); 1036 if(k <= a[u].size) { 1037 auto [w, z] = split(u, k); 1038 return {w, merge(z, v)}; 1039 } else { 1040 auto [w, z] = split(v, k - a[u].size); 1041 return {merge(u, w), z}; 1042 } 1043 } 1044 int find(int u, int k) { 1045 if(a[u].size == 1) return u; 1046 pushdown(u); 1047 if(k <= a[a[u].ls].size) return find(a[u].ls, k); 1048 else return find(a[u].rs, k - a[a[u].ls].size); 1049 } 1050 int build(int n) { 1051 if(n == 1) return newleaf(); 1052 int x = build(n / 2); 1053 int y = build(n - n / 2); 1054 return join(x, y); 1055 } 1056 int main() { 1057 std::ios::sync_with_stdio(false), std::cin.tie(0); 1058 std::cin >> n >> q; 1059 int rt = build(n); 1060 int lastans = 0; 1061 for(int i = 1; i <= q; i ++) { 1062 int o; 1063 std::cin >> o; 1064 if(o == 1) { 1065 int p; 1066 std::cin >> p; 1067 p = (p + lastans - 1) % n + 1; 1068 auto [A, B] = split(rt, p); 1069 setT(A, id[i] = newtag(i)); 1070 rt = merge(A, B); 1071 } else if(o == 2) { 1072 int p; 1073 std::cin >> p; 1074 p = (p + lastans - 1) % n + 1; 1075 auto [A, B] = split(rt, p); 1076 setR(A); 1077 rt = merge(A, B); 1078 } else if(o == 3) { 1079 int x; 1080 std::cin >> x; 1081 x = (x + lastans - 1) % q + 1; 1082 a[id[x]].exit = 0; 1083 } 1084 int p; 1085 std::cin >> p; 1086 p = (p + lastans - 1) % n + 1; 1087 int u = find(rt, p); 1088 std::cout << (lastans = get_val(u)) << '\n'; 1089 } 1090 return 0; 1091 } 1092 ```