So if you have attended ACTS Summer this year, you have probably asked yourself "Will there be an editorial for the entrance contest?". Well today is your lucky day because the answer to that question is "Yes". So get ready to read my editorial for the entrance contest that I wrote while waiting for my transfer flight in Istanbul while being extremely sleep deprived.
If $$$k = 1$$$ then the answer is obviously $$$(n - 1) \ A$$$, lets assume $$$k \ge 2$$$
Lemma: If $$$k | n$$$, its always optimal to do operation 2 and then continue, or to do $$$n - 1$$$ operation 1s and finish
Proof: Consider we use operation 2 on some $$$x \lt n$$$ then the cost of this is $$$(n - x) \ A + B$$$ and we reach point $$$x / k$$$, but if we do operation 2 right away we can reach point $$$x / k$$$ with $$$(n / k - x / k) \ A + B$$$ < $$$(n - x) \ A + B$$$. Hence its better to do operation 2 as soon as we can.
Using the Lemma we can come up with a simple algorithm that does operation 2 or tries to finish early when $$$k | n$$$ and bring $$$n$$$ to a multiple of $$$k$$$ with operation 1s otherwise.
If we consider a day $$$i$$$ such that the $$$4$$$ days before $$$i$$$ have the same value in the string. Then we have 4 cases, in each one of those cases it is trivial to deduce an inequality involving $$$T_{max}$$$ and $$$T_{min}$$$, in the end we get two ranges for $$$T_{max}$$$ and $$$T_{min}$$$ for which we can trivially find a pair with largest difference (The cases will be left as an exercise for the reader because I really cant be bothered to write them now)
Let $$$s(x)$$$ be the sum of digits of x. Its pretty clear that if the $$$x$$$ ends in exactly $$$k$$$ nines then $$$s(x) - s(x + 1) = 1 - 9 \ k$$$. Let $$$i$$$ be the smallest $$$1 \le i \le n$$$ such that $$$sum(i) - sum(i + 1)$$$ is minimized, then we can notice that the $$$ith$$$ number in the sequence will be the first number with the longest suffix of nines (lets denote this number of nines by $$$k$$$).
By using this we can notice that only the last $$$k+1$$$ digits can change in the sequence, We can also notice that the last $$$k$$$ digits are already uniquely determined due to us knowing that number at index $$$i$$$ ends in $$$k$$$ nines.
By setting the $$$k+1th$$$ digit to $$$0$$$ we will guarantee that all the changes in the digit sums will be compatible with the given array of digit sums. Now only is left to determine the rest of the digits, lets take a look at the $$$i+1th$$$ number, it will look like $$$x \ 10^k$$$, by setting $$$x$$$ to be any number such that $$$s(x) = sum_{i+1}$$$ we get a suitable value for the $$$i+1th$$$ number in the sequence and from there you can trivially find the start.
For a an index $$$i$$$ on which we do an OR operation, let $$$x$$$ be the xor of all the values of indices $$$j \gt i$$$ on which we do XOR operation, we can notice that that OR operation is the same as doing bitwise or of the final value with $$$A_i \oplus x$$$.
Lets process from right to left, we maintain two things: suffix xor of all XOR operations and bitmask of bits that are already set with OR operations. We can notice that its always optimal to do OR whenever we can because if we don't then we would have to set them somewhere in the future but if we do OR then we don't have to worry about them later.
So by simulating this we can just find a solution.
Lets sweep the height $$$h$$$ from $$$1$$$ to $$$n$$$.
Let $$$sum_j$$$ be the sum of all subarrays of size $$$h$$$ in column $$$j$$$.
Initially for $$$h = 1$$$ $$$sum_j = \sum_{i=1}^{n}a_i$$$.
When increasing the height from $$$h - 1$$$ to $$$h$$$ the contribution of row $$$i$$$ changes by:
+1, if $$$h-1 \le r \le n-h$$$;
-1, if $$$n-h \lt r \lt h-1$$$;
0, otherwise.
Therefore you can easily update $$$sum_j$$$ with prefix sums for each $$$j$$$ in $$$O(m)$$$ time.
After we have $$$sum_j$$$, rectangles are formed by $$$w$$$ consecutive columns. Hence the answer for a fixed $$$w$$$ is the sum of all subarrays of $$$sum_j$$$ with size $$$w$$$. We can compute this for all $$$1 \le w \le m$$$ with prefix sums analogous to the ones above.
Sweep the lifts from left to right.
For a fixed lift $$$i$$$ consider all orders whose ranges containing it. They are applied in increasing order of index.The lift jams in these two cases:
$$$|A_i - X_{t_1}| \gt P_i$$$
$$$|X_{t_{j}}- X_{t_{j-1}}| \gt P_i$$$ for some $$$j \ge 2$$$
Hence it is enough to maintain the minimal index order, and the absolute diference between the orders.
The first can be obviously be done with a std::set.
The second can be handled with a segtree, namely if $$$i$$$ is not included in the range order $$$j$$$ then then value of $$$j$$$ in the segtree is $$$-1$$$, otherwise its the absolute difference between it and the previous order. Then with a walk on the segment tree we can easily find the first position that is $$$ \gt P_i$$$ in $$$O(logQ)$$$.
Hence solving everything in $$$O((N+Q)logQ)$$$.
Let $$$f_i$$$ be the $$$ith$$$ Fibonacci number (note that we are using $$$f_1 = 1$$$ and $$$f_2 = 2$$$ ).
Let $$$Z_i = f_{a_i}$$$. We can notice that the operation is equivalent to picking index $$$i$$$ such that $$$Z_i$$$ and $$$Z_{i+1}$$$ are adjacent Fibonacci numbers and replace them with their sum.
With this its easy to prove that the largest size of crystal cannot exceed M = 70.
Let $$$(l, r, v)$$$ be a good triple if the range $$$[l, r]$$$ can be fully merged into a single value $$$v$$$.
Lemma: There are atmost $$$O(MN)$$$ good triples.
Consider fixing $$$l$$$ and $$$v$$$, let $$$j \ge i$$$ be the smallest number such that $$$\sum_{k=i}^{j} Z_k \ge f_v$$$, then we can notice that $$$j$$$ is unique for a choice of $$$(l, v)$$$ and due to the fact that $$$f_i \gt 0$$$ we can conclude that $$$(l, r, v)$$$ is the only good triple involving $$$(l, v)$$$ if and only if $$$\sum_{k=i}^{j} Z_k = f_v$$$ and there are no triples otherwise.
Hence there are at most $$$MN$$$ good triples.
Let $$$P_i^v$$$ be the position $$$j \ge i$$$ such that $$$\sum_{k=i}^{j} Z_k = f_v$$$ (if this $$$j$$$ does not exist $$$P_i^v = 0$$$).
We can compute all $$$P_i^v$$$ with two pointers in $$$O(MN)$$$
So to check that $$$(l, P_l^v, v)$$$ is good we need to either have:
$$$P_l^{v-1} \gt 0$$$ and $$$(l, P_l^{v-1}, v - 1)$$$ and $$$(P_l^{v-1} + 1, P_l^v, v - 2)$$$ are both good
$$$P_l^{v-2} \gt 0$$$ and $$$(l, P_l^{v-2}, v - 2)$$$ and $$$(P_l^{v-2} + 1, P_l^v, v - 1)$$$ are both good
So all good pairs can be precomputed with DP in $$$O(NM)$$$ time.
In the end just do $$$dp_i = $$$ minimal partitioning of $$$[0, i]$$$ with good triples.
Since there are atmost $$$O(NM)$$$ transitions and $$$O(N)$$$ states the total complexity is $$$O(NM)$$$.
If you find any mistakes, point them out in the comments :)
