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 was much harder than expected.

But it seems like people are complaining more about the narrow time limit, centered on 2116C - Gellyfish and Flaming Peony and 2115C - Gellyfish and Eternal Violet.

No one realized this before the contest, because none of the tester's code is get TLE except the wrong time complexity.

I actually don't see a problem with the Time Limit of 2116C - Gellyfish and Flaming Peony. Some of you may be puzzled, but let me try to explain this:

• 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.
• 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$$$.
• 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.
• 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), 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++.

For 2115C - Gellyfish and Eternal Violet, I'll admit it was a huge mistake:

• 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$$$.
• 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.
• In fact, the original constraints for 2115C - Gellyfish and Eternal Violet 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."

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.

Please think carefully about what happens after the death of either knight.

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.

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.

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.

Time complexity: $$$O(1)$$$ per test case.

Memory complexity: $$$O(1)$$$ per test case.

#include<bits/stdc++.h>

using namespace std;

inline void solve(){
	int a = 0, b = 0, c = 0, d = 0;
	scanf("%d %d %d %d", &a, &b, &c, &d);
	if(min(a, c) >= min(b, d)) printf("Gellyfish\n");
	else printf("Flower\n");
}

int T = 0;

int main(){
	scanf("%d", &T);
	for(int i = 0 ; i < T ; i ++) solve();
	return 0;
}

How to quickly compare $$$2^a + 2^b$$$ and $$$2^c + 2^d$$$ for given integers $$$a, b, c, d$$$ is the key.

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?

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)$$$.

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.

Time complexity: $$$O(n)$$$ per test case.

Memory complexity: $$$O(n)$$$ per test case.

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, Mod = 998244353;
int n = 0, s[N] = {}, p[N] = {}, q[N] = {}, r[N] = {};

inline void solve(){
	scanf("%d", &n);
	for(int i = 0 ; i < n ; i ++) scanf("%d", &p[i]);
	for(int i = 0 ; i < n ; i ++) scanf("%d", &q[i]);
	for(int i = 0, j = 0, k = 0 ; k < n ; k ++){
		if(p[k] > p[i]) i = k; if(q[k] > q[j]) j = k;
		if(p[i] != q[j]){
			if(p[i] > q[j]) printf("%d ", (s[p[i]] + s[q[k - i]]) % Mod);
			else printf("%d ", (s[q[j]] + s[p[k - j]]) % Mod);
		}
		else printf("%d ", (s[p[i]] + s[max(q[k - i], p[k - j])]) % Mod);
	}
	printf("\n");
}

int T = 0;

int main(){
	s[0] = 1; for(int i = 1 ; i < N ; i ++) s[i] = s[i - 1] * 2 % Mod;
	scanf("%d", &T);
	while(T --) solve();
	return 0;
}

Try to think about why Gellyfish can always achieve her goal, and ultimately what all the elements will turn into.

When you've figured out Hint 1, try using dynamic programming to reach your goal.

Let $$$g = \gcd(a_1, a_2, \dots, a_n)$$$, It can be shown that eventually all elements become $$$g$$$.

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$$$.

Further analysis reveals that $$$x$$$ cannot be less than $$$g$$$, no matter how it is manipulated. Thus we have $$$x = g$$$.

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$$$.

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$$$.

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.

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$$$.

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)}$$$.

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.

Time complexity: $$$O(n \max(a))$$$ per test case and $$$O(\max(a)^2)$$$ for preprocessing.

Memory complexity: $$$O(n+\max(a))$$$ per test case and $$$O(\max(a)^2)$$$ for preprocessing.

Try to solve $$$n, a_i \leq 2 \times 10^5$$$ with only one test case.

#include<bits/stdc++.h>

using namespace std;

const int N = 5000 + 5;

inline void checkmax(int &x, int y){
	if(y > x) x = y;
}

inline void checkmin(int &x, int y){
	if(y < x) x = y;
}

int n = 0, m = 0, k = 0, a[N] = {}, f[N] = {};
int g[N][N] = {}, ans = 0;

inline void solve(){
	scanf("%d", &n); m = k = 0;
	for(int i = 1 ; i <= n ; i ++){
		scanf("%d", &a[i]);
		k = g[k][a[i]];
	}
	memset(f, 0x3f, sizeof(f));
	for(int i = 1 ; i <= n ; i ++) a[i] /= k, checkmax(m, a[i]), f[a[i]] = 0;
	for(int x = m ; x >= 1 ; x --) for(int i = 1 ; i <= n ; i ++){
		int y = a[i];
		checkmin(f[g[x][y]], f[x] + 1);
	}
	ans = max(f[1] - 1, 0);
	for(int i = 1 ; i <= n ; i ++) if(a[i] > 1) ans ++;
	printf("%d\n", ans);
}

int T = 0;

int main(){
	for(int x = 0 ; x < N ; x ++) g[x][0] = g[0][x] = g[x][x] = x;
	for(int x = 1 ; x < N ; x ++) for(int y = 1 ; y < x ; y ++) g[x][y] = g[y][x] = g[y][x % y];
	scanf("%d", &T);
	while(T --) solve();
	return 0;
}

Try working backwards from the final sequence, to the initial.

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

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$$$?

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$$$.

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$$$.

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:

• It is not difficult to find that for $$$i \notin {x, y, z}$$$, $$$l'_i = l_i$$$.
• $$$l'_z = 0$$$, because the $$$c_z$$$ before the operation is overwritten, it will not actually have any restrictions.
• $$$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.

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$$$ .

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.

Time complexity: $$$O(n + q)$$$ per test case.

Memory complexity: $$$O(n + q)$$$ per test case.

#include<bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;
int n = 0, q = 0, a[N] = {}, b[N] = {}, c[N] = {};
int x[N] = {}, y[N] = {}, z[N] = {};

inline void init(){
	for(int i = 1 ; i <= n ; i ++) a[i] = b[i] = c[i] = 0;
	for(int i = 1 ; i <= q ; i ++) x[i] = y[i] = z[i] = 0;
	n = q = 0;
}

inline void solve(){
	cin >> n >> q;
	for(int i = 1 ; i <= n ; i ++){
		cin >> b[i];
		c[i] = b[i];
	}
	for(int i = 1 ; i <= q ; i ++) cin >> x[i] >> y[i] >> z[i];
	for(int i = q ; i >= 1 ; i --){
		int v = c[z[i]]; c[z[i]] = 0;
		c[x[i]] = max(c[x[i]], v), c[y[i]] = max(c[y[i]], v);
	}
	for(int i = 1 ; i <= n ; i ++) a[i] = c[i];
	for(int i = 1 ; i <= q ; i ++) c[z[i]] = min(c[x[i]], c[y[i]]);
	for(int i = 1 ; i <= n ; i ++) if(b[i] != c[i]){
		cout << "-1\n";
		return;
	}
	for(int i = 1 ; i <= n ; i ++) cout << a[i] << ' ';
	cout << '\n';
}

int T = 0;

int main(){
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T;
	for(int i = 0 ; i < T ; i ++) init(), solve();
	
	return 0;
}

Try to find an $$$O(nm h^2)$$$ solution using dynamic programming.

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?

Considering all current monsters, if the lowest HP of the monsters is $$$l$$$, Gellyfish can only make at most $$$l-1$$$ "ranged" attacks.

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)$$$.

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.

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.

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.

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)$$$.

Time complexity: $$$O(nmh)$$$ per test case.

Memory complexity: $$$O(nmh)$$$ per test case.

#include<bits/stdc++.h>

using namespace std;

const int N = 22, K = 4000 + 5, M = 400 + 5, Inf = 0x3f3f3f3f;

inline void checkmin(double &x, double y){
	if(y < x) x = y;
}

int n = 0, m = 0, s = 0, k = 0, p0 = 0, h[N] = {};
double p = 0, f[K][K] = {}, g[K][N][M] = {}, ans = 0;

inline void init(){
	for(int i = 0 ; i <= k ; i ++){
		for(int c = 0 ; c < n ; c ++) for(int x = 0 ; x <= m ; x ++) g[i][c][x] = 0;
		for(int x = 0 ; x <= s ; x ++) f[i][x] = 0;
	}
	m = Inf, s = 0, ans = 0;
}

inline void solve(){
	scanf("%d %d %d", &n, &k, &p0);
	p = 1.0 * p0 / 100;
	for(int i = 1 ; i <= n ; i ++){
		scanf("%d", &h[i]); h[i] --;
		m = min(m, h[i]);
	}
	for(int i = 1 ; i <= n ; i ++) s += h[i] - m;
	if(s > k){
	    printf("0.000000\n");
	    return;
	}
	g[0][0][0] = 1;
	for(int i = 1 ; i <= k ; i ++){
		g[i][0][0] = 1;
		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);
		for(int c = 1 ; c < n ; c ++){
			g[i][c][0] = g[i - 1][c][0] * p + g[i - 1][c - 1][0] * (1 - p);
			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);
		}
	}
	f[0][0] = 1;
	for(int i = 0 ; i < k ; i ++) for(int x = 0 ; x < s ; x ++){
		f[i + 1][x] += f[i][x] * p;
		f[i + 1][x + 1] += f[i][x] * (1 - p);
	}
	for(int i = s ; i <= k ; i ++){
		double r = 0;
		for(int x = 0 ; x <= min(i - s, m) ; x ++) r = max(r, g[k - i][0][m - x]);
		ans += r * f[i][s];
	}
	printf("%.6lf\n", ans);
}

int T = 0;

int main(){
	scanf("%d", &T);
	while(T --) init(), solve();
	return 0;
}

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.

"linear basis" is the answer to Hint 1. Please try to understand this: all addition operations are interpreted as XOR operations.

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$$$.

When $$$n = 0$$$, this is trivial: $$$f(x) = x$$$.

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:

• Not choosing $$$c_i$$$: result is $$$f(x)$$$
• Choosing $$$c_i$$$: result is $$$f(x + c_i) = f(x) + f(c_i) + b$$$.

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:

1. Whether we want to maximize or minimize the final answer
2. Whether the $$$k$$$-th bit of $$$f(x)$$$ is $$$0$$$ or $$$1$$$

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)$$$.

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$$$.

In each iteration, we try to insert $$$c_i$$$ into the linear basis, and associate it with a tag depending on the index $$$i$$$.

Time complexity: $$$O(n \log \max(a, b, x))$$$ per test case.

Memory complexity: $$$O(n + \log \max(a, b, x))$$$ per test case.

#include <bits/stdc++.h>
using i64 = long long;
constexpr int L = 60;
int main() {
	std::ios::sync_with_stdio(false), std::cin.tie(0);
	int T;
	for(std::cin >> T; T; T --) {
		int n; 
		std::cin >> n;
		std::vector<i64> a(n), b(n);
		std::string str;
		i64 all = 0;
		for(auto &x : a) std::cin >> x, all ^= x;
		for(int i = 0; i < n; i ++) {
			std::cin >> b[i];
			b[i] ^= a[i];
		}
		std::cin >> str;
		std::vector<i64> bas(L);
		std::vector<int> bel(L, -1);
		i64 ans = 0;
		for(int i = n - 1; i >= 0; i --) {
			i64 x = b[i], col = str[i] - '0';
			for(int i = L - 1; i >= 0; i --) if(x >> i & 1) {
				if(bas[i]) {
					x ^= bas[i];
				} else {
					for(int j = i - 1; j >= 0; j --) if(x >> j & 1) {
						x ^= bas[j];
					}
					bas[i] = x;
					for(int j = L - 1; j > i; j --) if(bas[j] >> i & 1){
						bas[j] ^= bas[i];
					} 
					bel[i] = col;
					break;
				}
			}
		} 

		for(int i = L - 1; i >= 0; i --) if(all >> i & 1) {
			all ^= bas[i];
		}
		for(int i = 0; i < L; i ++) if(bel[i] == 1) ans ^= bas[i];
		std::cout << (all ^ ans) << '\n';
	}
	
	return 0;
}

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$$$?

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$$$?

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$$$.

Let $$$z$$$ be the vertex in $$$s$$$ with the largest $$$\frac {w} {c}$$$, and $C = c_z, W = w_z$​.

Let's call your cards you don't get from vertex $$$z$$$ as special cards.

Lemma1. There exists an optimal solution such that the number of special cards does not exceed $$$C$$$.

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.

So it's not hard to find the total cost of special cards won't exceed $$$\max(c)^2$$$.

Now we can use dynamic programming to solve this problem:

• $$$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.

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$$$.

But unfortunately, the time complexity of the algorithm is $$$O(mn\max(c)^2)$$$. It's not fast enough.

At this point you'll find that solving the problem directly becomes incredibly tricky, so we'll try to split it into two problems.

We first consider the following problem: whether there is a better solution when $$$r$$$ is sufficiently large?

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}$$$.

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.

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:

• $$$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.

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$$$.

The time complexity becomes $$$O(mn \max(c))$$$, now it's fast enough.

For each query, we can just enumerate $$$v$$$ in $$$O(n)$$$ time complexity.

As for $$$r \leq max(c)^2$$$? It's an easy problem:

• $$$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.

The time complexity is $$$O(m \max(c)^2)​$$$.

For each query, we can get the answer directly from $$$f$$$ in $$$O(1)$$$ time complexity.

Over all, we have solved the problem.

Time complexity: $$$O(mn \max(c) + m \max(c)^2 + qn)$$$

Memory complexity: $$$O(n^2 \max(c) + n \max(c)^2)$$$

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll N = 200 + 5, Inf = 0xcfcfcfcfcfcfcfcf;

inline ll sqr(ll x){
	return x * x;
}

inline ll gcd(ll x, ll y){
	if(y) return gcd(y, x % y);
	else return x;
}

inline void checkmax(ll &x, ll y){
	if(y > x) x = y;
}

ll n = 0, m = 0, magic = 0, w[N] = {}, c[N] = {};
ll f[N][N * N] = {}, g[N][N][N][2] = {};
vector<vector<ll> > G(N);

inline void main_min(){
	memset(f, 0xcf, sizeof(f));
	for(ll x = 0 ; x <= magic ; x ++) f[1][x] = 0;
	for(ll u = 1 ; u <= n ; u ++){
		for(ll x = 0 ; x + c[u] <= magic ; x ++) checkmax(f[u][x + c[u]], f[u][x] + w[u]);
		for(ll v : G[u]) for(ll x = 0 ; x <= magic ; x ++) checkmax(f[v][x], f[u][x]);
	}
}

inline void solve_max(ll i){
	ll a = c[i], b = w[i];
	for(ll x = 0 ; x < a ; x ++) g[i][1][x][0] = 0;
	for(ll u = 1 ; u <= n ; u ++){
		if(u == i) for(ll x = 0 ; x < a ; x ++) checkmax(g[i][u][x][1], g[i][u][x][0]);
		else if(w[u] * a > c[u] * b) memset(g[i][u], 0xcf, sizeof(g[i][u]));
		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 ++){
			checkmax(g[i][u][(x + c[u]) % a][0], g[i][u][x][0] + w[u] - ((x + c[u]) / a) * b);
			checkmax(g[i][u][(x + c[u]) % a][1], g[i][u][x][1] + w[u] - ((x + c[u]) / a) * b);
		}
		for(ll v : G[u]) for(ll x = 0 ; x < a ; x ++){
			checkmax(g[i][v][x][0], g[i][u][x][0]);
			checkmax(g[i][v][x][1], g[i][u][x][1]);
		}
	}
}

inline void main_max(){
	memset(g, 0xcf, sizeof(g));
	for(ll i = 1 ; i <= n ; i ++) solve_max(i);
}

int main(){
	scanf("%lld %lld", &n, &m);
	for(ll i = 1 ; i <= n ; i ++){
		scanf("%lld %lld", &c[i], &w[i]);
		magic = max(magic, sqr(c[i]));
	}
	for(ll i = 1, u = 0, v = 0 ; i <= m ; i ++){
		scanf("%lld %lld", &u, &v);
		G[u].push_back(v);
	}
	main_min(), main_max();
	ll q = 0, p = 0, r = 0;
	scanf("%lld", &q);
	while(q --){
		scanf("%lld %lld", &p, &r);
		if(r <= magic) printf("%lld\n", f[p][r]);
		else{
			ll ans = Inf;
			for(ll i = 1 ; i <= n ; i ++){
				ll a = c[i], b = w[i];
				checkmax(ans, g[i][p][r % a][1] + (r / a) * b);
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

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.

• Type 1 and 2 operations can be handled directly by pushing into the appropriate segment’s queue or toggling a reversal flag.
• Type 3 (deletion) is handled by marking the element $$$x$$$ as deleted without immediately removing it from queues.

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.

For queries, we process the contribution from each round one by one. In each round:

1. Identify the segment that contains position $$$p$$$.
2. Iterate through the queue of that segment.
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.

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.

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})$$$

#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "\33[32m[" << __LINE__ << "]\33[m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
// template <typename T> T& read(T &x) {
// 	x = 0; int f = 1; char c = getchar();
// 	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
// 	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
// 	return x *= f;
// }
// bool be;
const int N = 1e5 + 1010, B = 500, B1 = N / B + 5, B2 = B + 5;
int n, q, ans, p[N], wp[N], tot, t[N], tl[N], tr[N];
bool rev[N];
bool ed[N];
// bool vv[N];
// struct Q1 {
// 	int tl = 1, tr;
// 	int a[B2];
// 	bool chk() {
// 		return tl <= tr;
// 	}
// 	int front() {
// 		return a[tl];
// 	}
// 	void pop() {
// 		tl++;
// 	}
// 	void push(int x) {
// 		a[++tr] = x;
// 	}
// } tq[N];
// struct Q2 {
// 	int tl = 1, tr;
// 	int a[B1];
// 	bool chk() {
// 		return tl <= tr;
// 	}
// 	int front() {
// 		return a[tl];
// 	}
// 	void pop() {
// 		tl++;
// 	}
// 	void push(int x) {
// 		a[++tr] = x;
// 	}
// } vq[N];
queue <int> tq[N], vq[N];
vector <int> cur;
int qq(int x) {
	while (tq[x].size()) {
		if (!ed[tq[x].front()]) return tq[x].front();
		tq[x].pop();
	}
	return 0;
}
int query(int x) {
	int s = 0;
	for (int i: cur) {
		s += tr[i] - tl[i] + 1;
		if (s >= x) {
			int g = s - x + 1;
			int y;
			if (rev[i]) {
				y = p[tl[i] + g - 1];
			} else {
				y = p[tr[i] - g + 1];
			}
			while (vq[y].size()) {
				int tmp = qq(vq[y].front());
				if (tmp) return tmp;
				vq[y].pop();
			}
			// int tmp = qq(i);
			// if (~tmp) return tmp;
			return qq(i);
		}
	}
	assert(false);
	// return -1;
}
// bool ee;
// int cnt = 0;
signed main() {
	ios::sync_with_stdio(0); // don't use puts
	cin.tie(0), cout.tie(0);
	// debug << abs(&ee - &be) / 1024 / 1024 << endl;
	cin >> n >> q;
	F(i, 1, n) p[i] = i;
	cur.push_back(++tot);
	tl[1] = 1, tr[1] = n;
	F(i, 1, q) {
		int f, x, y; cin >> f >> x >> y;
		if (f == 3) {
			x = (x + ans - 1) % q + 1;
		} else {
			x = (x + ans - 1) % n + 1;
		}
		y = (y + ans - 1) % n + 1;
		// auto split = [&] (int x) {
		// 	if (x > n || vv[x]) return;
		// 	// vv[x] = true;
		// 	for (auto [])
		// };
		if (f == 1) {
			int s = 0;
			for (int j: cur) {
				int w = tr[j] - tl[j] + 1;
				s += w;
				if (s >= x) {
					if (s > x) {
						tot++;
						tq[tot] = tq[j];
						int g = s - x;
						if (rev[tot] = rev[j]) {
							tl[tot] = tl[j];
							tr[tot] = (tl[j] += g) - 1;
						} else {
							tr[tot] = tr[j];
							tl[tot] = (tr[j] -= g) + 1;
						}
						cur.insert(next(find(all(cur), j)), tot);
					}
					tq[j].push(i);
					break;
				}
				tq[j].push(i);
			}
		}
		if (f == 2) {
			int s = 0, sz = 0;
			for (int j: cur) {
				sz++;
				int w = tr[j] - tl[j] + 1;
				s += w;
				if (s >= x) {
					if (s > x) {
						tot++;
						tq[tot] = tq[j];
						int g = s - x;
						if (rev[tot] = rev[j]) {
							tl[tot] = tl[j];
							tr[tot] = (tl[j] += g) - 1;
						} else {
							tr[tot] = tr[j];
							tl[tot] = (tr[j] -= g) + 1;
						}
						cur.insert(next(find(all(cur), j)), tot);
					}
					reverse(cur.begin(), cur.begin() + sz);
					F(j, 0, sz - 1) rev[cur[j]] ^= true;
					break;
				}
			}
		}
		if (f == 3) {
			if (x < i) ed[x] = true;
		}
		cout << (ans = query(y)) << '\n';
		if (cur.size() >= B) {
			int cnt = 0;
			for (int j: cur) {
				if (rev[j]) {
					DF(k, tr[j], tl[j]) {
						vq[wp[++cnt] = p[k]].push(j);
					}
				} else {
					F(k, tl[j], tr[j]) {
						vq[wp[++cnt] = p[k]].push(j);
					}
				}
			}
			F(j, 1, n) {
				p[j] = wp[j];
			}
			cur.clear();
			cur.push_back(++tot);
			tl[tot] = 1, tr[tot] = n;
		}
		// for (int j: cur) {
		// 	debug << tl[j] << " " << tr[j] << " " << rev[j] << endl;
		// }
	}
	return 0;
}

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.

To address this, we split each set $$$S_u$$$ into two components:

1. $$$T_u$$$: A part of $$$S_u$$$ stored directly at node $$$u$$$
2. A collection of child nodes $$$v_{u,1}, v_{u,2}, \cdots, v_{u,k}$$$, each storing a subset of $$$S_u$$$

We maintain the invariant: $$$S_u = T_u + \sum_{i=1}^k S_{v_{u,i}}$$$.

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.

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}$$$.
2. Type 2 (Reverse a segment): Just mark the root of the relevant subtree with a "reverse" flag.
3. Type 3 (Delete): Since each element $$$x$$$ appears in only one $$$T$$$, we can directly remove it from that node's $$$T$$$.

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}})$$$

Thus, we can sequentially check whether each $$$S_{v_{u,i}}$$$ is empty.

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:

• Nodes with $$$|S_x| \ne 0$$$: We only encounter one such node per query — this is where we find the minimum value.
• 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.
• 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.

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.

Time complexity: $$$O(q \log n + n)$$$.

Memory complexity: $$$O(q \log n + n)$$$.

#include <bits/stdc++.h>
constexpr int N = 3e5 + 10, S = 1.1e7, SS = 2 * S;
int n, q;
int next[SS], val[SS], cnt;
struct queue {
	int head, tail;
	void push(int x) {
		if(head) {
			next[tail] = ++ cnt, val[cnt] = x; tail = cnt;
		} else {
			head = tail = ++ cnt, val[cnt] = x;
		}
		assert(cnt < SS - 100);
	}
	void pop() {head = next[head];}
	int front() {return val[head];}
	bool check() {return head == tail;}
	bool empty() {return head == 0;}
	void clear() {head = tail = 0;}
};
struct node {
	int ls, rs;
	queue fa;
	int val, exit;
	int size, rev;
}a[S];
int tot;
int id[N];
void pushup(int u) {
	a[u].size = a[a[u].ls].size + a[a[u].rs].size;
}
void setR(int u) {
	a[u].rev ^= 1;
	std::swap(a[u].ls, a[u].rs);
}
void setT(int u, int v) {
	a[u].fa.push(v);
}
void pushdown(int u) {
	if(a[u].rev) {
		setR(a[u].ls);
		setR(a[u].rs);
		a[u].rev = 0;
	}
}
int newnode() {
	int u = ++ tot;
	a[u].exit = 2;
	return u;
}
int newleaf() {
	int u = newnode();
	a[u].size = 1;
	return u;
}
int join(int x, int y) {
	int u = newnode();
	a[u].ls = x, a[u].rs = y;
	a[x].fa.push(u);
	a[y].fa.push(u);
	pushup(u);
	return u;
}
auto cut(int x) {
	pushdown(x);
	a[x].exit = 1;
	return std::make_pair(a[x].ls, a[x].rs);
}
int get_val(int u) {
	if(a[u].exit == 0) return 0;
	if(a[u].val != 0) return a[u].val;
	if(a[u].fa.empty()) return 0;
	int ans = 0;
	while(1) {
		ans = get_val(a[u].fa.front());
		if(ans) return ans;
		if(a[u].fa.check()) break;
		a[u].fa.pop();
	}
	if(a[u].exit == 1) {
		a[u].exit = 0;
		a[u].fa.pop();
		a[u].fa.clear();
	}
	return 0;
}
int newtag(int x) {
	int u = ++ tot;
	a[u].val = x;
	a[u].exit = 1;
	return u;
}
constexpr double ALPHA = 0.292;
bool too_heavy(int sx, int sy) {
	return sy < ALPHA * (sx + sy);
}
int merge(int x, int y) {
	if(!x || !y) return x + y;
	if(too_heavy(a[x].size, a[y].size)) {
		auto [u, v] = cut(x);
    	if(too_heavy(a[v].size + a[y].size, a[u].size)) {
    		auto [z, w] = cut(v);
    		return merge(merge(u, z), merge(w, y));
   		} else {
    		return merge(u, merge(v, y));
    	}
  	} else if(too_heavy(a[y].size, a[x].size)) {
		auto [u, v] = cut(y);
		if(too_heavy(a[u].size + a[x].size, a[v].size)) {
			auto [z, w] = cut(u);
			return merge(merge(x, z), merge(w, v));
		} else {
			return merge(merge(x, u), v);
		}
	} else {
		return join(x, y);
	}
}
std::pair<int, int> split(int x, int k) {
	if(!x) return {0, 0};
	if(!k) return {0, x};
	if(k == a[x].size) return {x, 0};
	auto [u, v] = cut(x);
	if(k <= a[u].size) {
		auto [w, z] = split(u, k);
		return {w, merge(z, v)};
	} else {
		auto [w, z] = split(v, k - a[u].size);
		return {merge(u, w), z};
	}
}
int find(int u, int k) {
	if(a[u].size == 1) return u;
	pushdown(u);
	if(k <= a[a[u].ls].size) return find(a[u].ls, k);
	else return find(a[u].rs, k - a[a[u].ls].size);
}
int build(int n) {
	if(n == 1) return newleaf();
	int x = build(n / 2);
	int y = build(n - n / 2);
	return join(x, y);
}
int main() {
	std::ios::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> n >> q;
	int rt = build(n);
	int lastans = 0;
	for(int i = 1; i <= q; i ++) {
		int o;
		std::cin >> o;
		if(o == 1) {
			int p;
			std::cin >> p;
			p = (p + lastans - 1) % n + 1;
			auto [A, B] = split(rt, p);
			setT(A, id[i] = newtag(i));
			rt = merge(A, B);
		} else if(o == 2) {
			int p;
			std::cin >> p;
			p = (p + lastans - 1) % n + 1;
			auto [A, B] = split(rt, p);
			setR(A);
			rt = merge(A, B);
		} else if(o == 3) {
			int x;
			std::cin >> x;
			x = (x + lastans - 1) % q + 1;
			a[id[x]].exit = 0;
		} 
		int p;
		std::cin >> p;
		p = (p + lastans - 1) % n + 1;
		int u = find(rt, p);
		std::cout << (lastans = get_val(u)) << '\n';
	}
	return 0;
}