Congratulations um_nik pulling this 5 seconds before the end of the contest

Note that for the operation $$$a\ b$$$, you can independently flip the indices for the height and the width respectively. So specifically, consider the first sample. We initially start with the indices $$$[0, 1, 2, 3, 4]$$$ for the height. When we apply the operation 3, we flip the first 3 and the last 2 to get $$$[2, 1, 0, 4, 3]$$$. You can verify that within each row, the original indices of each letter corresponds to this array, both the original position from the top and from the left.

So the question is, can we compute these arrays for the height and width efficiently, and then we can just print out the result using these indices. The observation that we can make is that the operation flipping by $$$x$$$ is equivalent to

1. rotating the index array right by $$$x$$$
2. reversing the entire array

We can also perform the reversal first, which gives us the equivalent set of instructions:

1. reversing the entire array
2. rotating the index array right by $$$len - x$$$ (where $$$len$$$ is either the height or width depending on which array it is)

If we do two operations in a row, then we can do the reversals for both operations one right after the other, so they cancel out. So operation $$$x$$$ followed by operation $$$y$$$ is rotating right by $$$x$$$, then by $$$len - y$$$. We can do this to simulate an even number of operations, and if $$$Q$$$ is odd, we can just directly simulate the last step.

Solution code can be found here.

In C++ you can complete all reverse queries with __gnu_cxx::rope<int> in $$$O(log(n))$$$. My accepted solution.

Reverse $$$[i,j)$$$ is equal to swap segment $$$[i,j)$$$ in direct order of items with segment $$$[n-j,n-i)$$$ in reversed order of items. The rope can erase and insert segments in $$$O(log(n))$$$.

I treat a cell at $$$(1,1)$$$ as pivot point. By knowing the position of this pivot cell at the end, we can determine the rest of the positions

You can do it without and data structure. You had to figure that rows and columns are independent and final transformation is the cycle of identity permutation.

Same.
I copied this https://mirror.codeforces.com/blog/entry/47186?#comment-403709 and converted to C++.
Although treap is a overkill as editorial is much simpler

In C++ you can use __gnu_cxx::rope<int>. AC submission. Comment about this

I use brute force.

Since $$$S_1 = S_2$$$, $$$S_5 = S_6$$$ and $$$S_7 = S_9$$$, therefore we only need to iterate 6 different indices in $$$S$$$ (only $$$10^6$$$ digits possible)

Your solution is correct (I implemented it and got AC). There are a couple of things I would like to say:

1. We have 2 cases. If S > R, then we can simply set x[i] = x[i] — (S-R). This should be $$$x[0] = x[0] - (S - R)$$$, not $$$x[i] = x[i] - (S - R)$$$.

2. If in the end S != R, then if sum of A[i] = 0, we know for sure there is no answer. This is true, but unnescessary. We can just check for answer in the other direction and if there still is no answer found, we print "No".

3. When implementing the code, make sure to use long long instead of int, the integers will get very large.

I won't link my code here, because it's messy and I don't want to spoil the implementation part for you. If you need any help, I'll be glad to help!

To view problem ratings, go to the ARC section here.