codeforces-scrape

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

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 ```