You should know only one fact to solve this task: . This fact can be proved by the truth table. Let's use this fact: . Also . According two previous formulas we can get that f(a, 1, n) ≥ f(a, i, j). Finally we can get the answer. It's equal to f(a, 1, N) + f(b, 1, N).
Let's define timeR i as a number of last query, wich repaint row with number i, timeC j – as number of last query, wich repaint column with number j. The value in cell (i, j) is equal a max(timeR i, timeC j).
If we have some pair of queries that r i ≥ r j, i > j, then we can skip query with number j. Let's skip such queries. After that we get an array of sorted queries ( r i ≤ r j, i > j). Let's sort subarray a 1..max(r i) and copy it to b. For proccessing query with number i we should record to a r i - 1..r i first or last(it depends on t i - 1) r i - 1 - r i + 1 elementes of b. After that this elements should be extract from b. You should remember that you need to sort subarray a 1..r n, after last query.
Let's define S [i] as i - th block of S, T [i] — as i - th block of T.Also S [l..r] = S [l]S [l + 1]...S [r] and T [l..r] = T [l]T [l + 1]...T [r].
T is substring of S, if S [l + 1..r - 1] = T [2..m - 1] and S [l].l = T .l and S [l].c ≥ T .c and S [r].l = T [m].l and S [r].c ≥ T [m].c. Let's find all matches of T [l + 1..r - 1] in S and chose from this matches, witch is equal T.You can do this by Knuth–Morris–Pratt algorithm.
This task has a some tricky test cases:
- and . Letters in the adjacent blocks are may be same.This problem can be solved by the union of adjacent blocks with same letter.
- and . Count of T blocks are less than 3. Such cases can be proccess singly.
and . Answer for this test should be stored at long long.
The operation, which has been described in the statement, is cyclic shift of some subarray. Let's try to solve this problem separately for left cyclic shift and for right cyclic shift. Let's define as answer before(or without) cyclic shift, Δans = ans - ans' — difference between answer after cyclic shift and before. This difference can be found by next formulas:
For left cyclic shift:
Δ l, r = (a l·r + a l + 1·l + ... + a r·(r - 1)) - (a l·l + a l + 1·(l + 1) + ... + a r·r) = a l·(r - l) - (a l + 1 + a l + 2 + ... + a r)
For right cyclic shift:
Δ' l, r = (a l·(l + 1) + a l + 1·(l + 2) + ... + a r·l) + (a l·l + a l + 1·(l + 1) + ... + a r·r) = (a l + a l + 1 + ... + a r - 1) + a r·(l - r)
You can find this values with complexity , using prefix sums, .
Let's try to rewrite previous formulas:
For left cyclic shift: Δ l, r = (a l·r - sum r) + (sum l - a l·l)
For right cyclic shift: Δ' l, r = (a r·l - sum l - 1) + (sum r - 1 - a r·r)
You can see, that if you fix l for left shift and r for right shift, you can solve this problem with complexity using Convex Hull Trick.