Official

G - Keyboard Editorial by en_translator

There are various ways to solve this problem. If \(N\) were on the order of \(10^5\), a square-root decomposition approach would be efficient. However, in this problem we are given the constraint \(N \leq 8 \times 10^6\) and a very tight execution time limit, so that approach is not sufficient. By the way, there is an interesting alternative solution where we store persistent balanced binary trees on a segment tree; this approach does allow us to solve the problem with a clever implementation. If you are familiar with data structures, give it a try.
In this editorial, we will introduce a solution using, simply put, an interesting segment tree that can merge data structures that do not seem mergeable at a glance. If you tried a segment tree approach but could not come up with how to implement merging, we strongly recommend you to read this article.

First of all, we will explain a TLE (Time Limit Exceeded) solution using an ordinary segment tree.
For a string \(S\), define \(\mathrm{normalize}(S)\) as follows:

  • Repeat removing from \(S\) a substring of the form (digit) + B as many times as possible in any order. Let \(\mathrm{normalize}(S)\) be the resulting \(S\).

For example, if \(S=\) 1BB234B567, we have \(\mathrm{normalize}(S)=\) B23567. We say this string \(\mathrm{normalize}(S)\) is “normalized.”
\(\mathrm{normalize}(S)\) has the following property:

  • If you remove leading B’s from \(\mathrm{normalize}(S)\), the resulting sequence coincides with \(f(S)\). (In other words, the sought answer \(f(S)\) can be obtained from \(\mathrm{normalize}(S)\).)
  • For normalized strings \(S\) and \(T\), define an operator \(\oplus\) by \(S \oplus T := \mathrm{normalize}(S+T)\). Then the set of normalized strings forms a monoid under the binary operation \(\oplus\), with the empty string as the identity element.
  • For any strings \(S\) and \(T\), we have \(\mathrm{normalize}(S+T) = \mathrm{normalize}(\mathrm{normalize}(S) + \mathrm{normalize}(T))\).

These facts yield a solution that puts \(\mathrm{normalize}(S)\) on the nodes of a segment tree. But of course, this solution leads to TLE because:

  • \(\mathrm{normalize}(S)\) can have a length of \(N\), incurring \(\mathrm{\Omega}(N)\) for finding the product of nodes and answering a segment-product query.

To tackle this issue, let us try to minimize the information that \(\mathrm{normalize}(S)\) stores. Specifically, consider the Data type storing the following three parameters:

  • \(b\): the number of leading B’s in \(\mathrm{normalize}(S)\).
  • \(l\): the length of \(\mathrm{normalize}(S)\) except for its leading B’s (i.e. the length of \(f(S)\)).
  • \(x\): the value of \(\mathrm{normalize}(S)\) except for its leading B’s (i.e. the value of \(f(S)\)) interpreted in decimal, modulo \(998244353\).

For example, if BB12456\(\mathrm{normalize}(S)=\), we have \(b=2, l=5\), and \(x=12456\).

This Data type requires only \(\mathrm{O}(1)\) space, so the issues above have been resolved, but instead we are no longer able to find the product of Data. For example, the product of B1234567891 and BBBBBBB456 is B123456, but if they are reduced to Data-type values \((1,10,236323538)\) and \((7,3,456)\), you are no longer able to find their products (because the tuple \((1,10,236323538)\) does not maintain the information that the last \(7\) digits of B1234567891 is 4567891.)

In the general case, the data becomes no longer a monoid by reducing the information in this way, making impossible to store it on a segment tree. However, in this problem, the point is that the product of Data type values can be computed in \(\mathrm{O}(\log N)\) as long as the left operand is stored on the segment tree.

What enables us to compute the product is that the process of merger of Data-type values is persisted on the segment tree, and traversing it gives us more details on the data.
Suppose that a Data \(d_1\) is stored on the segment tree. If we can obtain “the integer, modulo \(998244353\), formed by the last \(n\) digits of the string corresponding to \(d_1\),” then we can compute the product of \(d_1\) and \(d_2\). In fact, we can perform a binary search over the descendants of \(d_1\) to obtain that desired value in \(\mathrm{O}(\text{distance from }d_1\text{ to the leaf}) = \mathrm{O}(\log N)\) time! For more details, please refer to the procedure explained in the following psuedocode.

# This function returns the integer, modulo 998244353, formed by the last n digits of the string corresponding to the data stored as the i-th element of the array managing the information on the segment tree.
# The index of the children of the node for the i-th element is assumed to be the 2i-th and (2i+1)-th elements (if present).
# We define TEN[i] = 10^i mod 998244353 and ITEN[i] = 10^{-i} mod 998244353.  The first (N+1) elements of these arrays are precalculated.
def dfs(i, n):
  assert seg[i].l >= n
  if n == 0: return 0
  if seg[i].l == n: return seg[i].x
  # At this point, the existence of the children of vertex i is guaranteed.

  # If the right child has an enough number of digits, return that
  if seg[2 * i + 1].l >= n: return dfs(2 * i + 1, n)

  # Otherwise, we want m more digits.
  m = n - seg[2 * i + 1].l
  # However, the last b digits of seg[2 * i] is erased by B's in seg[2 * i + 1]
  b = seg[2 * i + 1].b
  # Thus, we need to compute (m+b) digits and cancel the last b digits
  y = dfs(2 * i, m + b)
  # Reconstruct the last b digits
  z = seg[2 * i].x - (seg[i].x - seg[2 * i + 1].x) * ITEN[seg[2 * i + 1].l] * TEN[b]

  return (y - z) * ITEN[b] * TEN[seg[2 * i + 1].l] + seg[2 * i + 1].x

By internally calling this routine, the product can be computed in \(\mathrm{O}(\log N)\) time when the left operand is stored in the segment tree. Therefore, every query against the segment tree can be processed in \(\mathrm{O}(\log^2 N)\).

The initialization of the segment tree can be done in \(O(N)\) with a \(\log\) factor (the proof is left as an exercise of complexity analysis to the reader), so the problem can be solved in a total of \(\mathrm{O}(N + Q \log^2 N)\), which is fast enough.

posted:
last update: