Official

G - Triple Index Editorial by en_translator


When we know

  • the number of occurrences of each integer, and
  • the number of triples \((i, j, k)\) that satisfies the conditions in the problem statement

within a segment \([l, r]\) of the sequence \(A\), we can obtain the two numbers for a new segment whose left or right end is different by one in an \(O(1)\) time by delta update. Thus, we can use Mo’s algorithm to solve this problem.

What is Mo’s algorithm?

We will briefly explain Mo’s algorithm. Let \(N\) be the length of sequence \(A\) we are interested in, with the \(0\)-based indexing like \((A_0, A_1, \ldots, A_{N-1})\). Also, we assume the following property.

When the answer to a query against a segment \([l, r]\) (which we simply call query \([l, r]\)) is known, we can obtain the answer to a query against a new segment whose left or right end is different by one fast enough (here, for simplicity, assumed \(O(1)\) time).

After answering a query \([l, r]\), we can repeatedly increment or decrement \(l\) or \(r\) to change the left end \(l \rightarrow l'\) and right end \(r \rightarrow r'\) in order to find the answer to the next query \([l', r']\) in an \(O(|l'-l| + |r'-r|)\) time.

If we naively adopt this way to answer the queries \([l_1, r_1], [l_2, r_2], \ldots, [l_Q, r_Q]\) in the given order, each transformation \([l_i, r_i] \rightarrow [l_{i+1}, r_{i+1}]\) costs a total of \(\Theta(QN)\) time over all queries at worst; Mo’s query tries to optimize the process by cleverly rearranging the queries. (Thus, all queries have to be given beforehand.)

Specifically, we define the order of answering \(Q\) queries \([l, r]\) as follows:

For a fixed integer \(B\), queries with smaller \(\lfloor l / B \rfloor\) are answered earlier; if \(\lfloor l/ B\rfloor\) are the same, those with smaller \(r\) are answered earlier.

We evaluate the time complexity of this algorithm as follows.

First, we count how many times \(l\) is shifted.

  • Transformations such that \(\lfloor l_i/ B\rfloor = \lfloor l_{i+1}/ B\rfloor\) occurs \(O(Q)\) times in total, each of which shifts the left end by \(O(B)\) amount.

  • Transformations such that \(\lfloor l_i/ B\rfloor \lt \lfloor l_{i+1}/ B\rfloor\) occurs \(O(N/B)\) times in total, each of which shifts the right end by \(O(N)\) amount.

Then we consider how many times \(r\) is shifted. Among the transformations \([l_i, r_i] \rightarrow [l_{i+1}, r_{i+1}]\),

  • we first consider those such that \(\lfloor l_i/ B\rfloor = \lfloor l_{i+1}/ B\rfloor\). Within the queries with the same \(\lfloor l/ B\rfloor\), they are sorted in ascending order of \(r\); that is, while the group of queries with the same \(\lfloor l/ B\rfloor\) is processed, \(r\) increases monotonically. Thus, the right end shifts \(O(N)\) times for each group of queries with the same \(\lfloor l/ B\rfloor\). Since there are \(O(N/B)\) distinct possible values for \(\lfloor l/ B\rfloor\), i.e. there are \(O(N/B)\) groups, so the right end shifts \(O(N^2/B)\) times in total.

  • those such that \(\lfloor l_i/ B\rfloor \lt \lfloor l_{i+1}/ B\rfloor\) occurs \(O(N/B)\) times, each of which costs \(O(N)\) times to shift them.

Therefore, the algorithm runs in a total of \(O(QB + N^2/B)\) time. By taking \(B\) around \(N/\sqrt{Q}\), the problem can be solved in a total of \(O(N\sqrt{Q})\) time.

posted:
last update: