Imagine the product of a₀x⁰, a₁x¹, ..., a_n - 1x^n - 1 and b₀x⁰, b₁x^- 1, ..., b_n - 1x^{- n + 1}. If a_i is 1 if s[i] is A and b_i is 1 if s[i] is B, then the coefficients of xⁱ would be the answer for i-inversions.

You can shift the second expression to get a valid polynomial (get non-negative exponents multiplying it by x^j). Then you can solve it by FFT. If you shifted by j, then answer for k-inversion will be coefficient of x^j + k.

B: Suppose you know the number of digits for each start and end, then it is easy. We can assume they have 1 digit at first, then get the answer, and then you may find some start/end need more digits. Then you can update them and solve again. You do this again and again till it will not change. Each start/end can only increase few times, so the complicity is O(n^2 * log(n))

J: For each grid square, we can compute, what is the latest time a marker has went over this square?

Now, for a square that needs to be colored, the marker can't dry out before the latest time we touch this square, so we know the minimum time the marker needs to dry out is at least the maximum of all these values.

On the other hand, for a square to be blank, the marker needs to dry out before the latest time we touch this square, so we know the maximum time the marker can dry out is at most the minimum of all these values.

If minimum time > maximum time, it's impossible, otherwise, we can output these two numbers. Of course, computing the latest time the marker hits each square is the tricky part, but one hint is to use segment trees.

Here! : https://naipc16.kattis.com/problems