Original proposer: admin

Cumulative sums

Consider the following problem.

Problem: you are given many queries of the following form: “how many \(a\)’s are there from the \(l\)-th through \(r\)-th characters of \(S\)?” Answer them.

Let \(X_i\) be the number of \(a\) contained in the first \(i\) characters of \(S\). Then \(X_0,\ldots,X_N\) can be computed consecutively in ascending order of \(i\) in \(O(N)\) time, in the following way:
\(X_i=\begin{cases} 0 & i=0\\ X_{i-1} & S_i\neq a\\ X_{i-1}+1 & S_i=a \end{cases}\)

This \(X\) allows us to count the number of \(a\)’s within the \(l\)-th through \(r\)-th characters of \(S\): the sought count is \(X_r-X_{l-1}\), which can be computed in \(O(1)\) time.

Binary search

By precalculating the cumulative sums, we can assume that we can count the number of occurrences of a and b in any subarray in \(O(1)\) time.

For a fixed \(l\), consider how many \(r\) satisfies the conditions.

• The larger \(r\) is, the more a’s are contained in \([l,r]\). Thus, if we define \(a_l\) as “the minimum \(r\) such that \([l,r]\) contains \(A\) or more as,” the condition on a is equivalent to \(r \geq a_l\).
• The larger \(r\) is, the more b’s are contained in \([l,r]\). Thus, if we define \(b_l\) as “the maximum \(r\) such that \([l,r]\) contains less than \(B\) b’s,” then the condition on b is equivalent to \(r\leq b_l\).

One can find \(a_l\) and \(b_l\) with binary search in \(O(\log N)\) time, and the number of integers \(r\) satisfying the condition is \(\max(0,b_l-a_l+1)\). (When implementing, beware that there may be cases where “the minimum \(r\) such that \([l,r]\) contains \(A\) or more as.”

By performing this for all \(l\), the problem can be solved in a total of \(O(N\log N)\) time.

Moreover, the values \(a_l\) and \(b_l\) defined here are monotonically increasing with respect to \(l\), so the problem can even be solved in \(O(N)\) time.