As explained in the editorial for Problem E, the key to solving a segment tree problem is to design the necessary information \(f(X)\) about a sequence \(X\) and a function \(\mathrm{op}\) satisfying

\[\mathrm{op}(f(X), f(Y)) = f(XY)\]

Let us consider how to solve this problem with this principle in mind.

We want the maximum length of a contiguous subsequence of \(X\) consisting of equal elements. Such a contiguous subsequence is called a run, so we denote this value by \(\mathrm{RUN}(X)\).

Consider the information about \(X, Y\) needed to compute \(\mathrm{RUN}(XY)\). A run in \(XY\) can be one of the following \(3\) types:

• A run entirely contained in \(X\).
• A run formed by joining a run that is a suffix of \(X\) and a run that is a prefix of \(Y\).
• A run entirely contained in \(Y\).

With this in mind, define the following functions:

• \(\mathrm{plen}(X)\): The length of the run forming a prefix of \(X\).
• \(\mathrm{slen}(X)\): The length of the run forming a suffix of \(X\).
• \(L(X)\) and \(R(X)\): The leftmost and rightmost elements of \(X\), respectively.

With this information, we can compute \(\mathrm{RUN}(XY)\) as follows:

\[ \mathrm{RUN}(XY) = \begin{cases} \max \lbrace\mathrm{RUN}(X), \mathrm{RUN}(Y)\rbrace & R(X) \neq L(Y) \\ \max \lbrace\mathrm{RUN}(X), \mathrm{RUN}(Y), \mathrm{slen}(X) + \mathrm{plen}(Y)\rbrace & R(X) = L(Y) \end{cases} \]

At first, using \(\mathrm{RUN}(X), \mathrm{plen}(X), \mathrm{slen}(X), \mathrm{L}(X), \mathrm{R}(X)\) as \(f(X)\) looks sufficient, but it does not work.

As stated above, \(\mathrm{op}\) must satisfy

\[\mathrm{op}(f(X), f(Y)) = f(XY)\]

so we must be able to compute the whole of \(f(XY)\) from \(f(X), f(Y)\). Examining this requirement more closely, we find that we cannot compute \(\mathrm{plen}(XY), \mathrm{slen}(XY)\) from \(f(X), f(Y)\) as they stand. Since these two cases are symmetric, we explain only \(\mathrm{plen}(XY)\). The value of \(\mathrm{plen}(XY)\) is as follows:

• If the whole of \(X\) is a run and \(\mathrm{R}(X)=\mathrm{L}(Y)\), then \(\mathrm{plen}(XY) = \mathrm{plen}(X) + \mathrm{plen}(Y)\).
• Otherwise, \(\mathrm{plen}(XY) = \mathrm{plen}(X)\).

Thus, to compute \(\mathrm{plen}(XY)\), we additionally need to know whether the whole of \(X\) is a run.

To compute \(\mathrm{plen}(XY), \mathrm{slen}(XY)\) inside \(\mathrm{op}\), let us add, for example,

• \(\mathrm{len}(X)\): The length of the sequence \(X\)

to the information in \(f(X)\). Then

\[ \mathrm{plen}(XY) = \begin{cases} \mathrm{plen}(X) + \mathrm{plen}(Y) & \mathrm{plen}(X) = \mathrm{len}(X) \wedge \mathrm{R}(X) = \mathrm{L}(Y)\\ \mathrm{plen}(X) & \mathrm{otherwise} \end{cases} \]

holds, allowing us to compute \(\mathrm{plen}(XY)\) from \(f(X), f(Y)\). (The same applies to \(\mathrm{slen}(XY)\).)

These observations give the monoid implemented below. (The \(\mathrm{RUN}\) function corresponds to the variable best.)

struct S {
  int len, plen, slen, L, R, best;
};

S op(S x, S y) {
  if (x.len == 0) return y;
  if (y.len == 0) return x;
  S z{x.len + y.len, x.plen, y.slen, x.L, y.R, max(x.best, y.best)};
  if (x.R == y.L) {
    z.best = max(z.best, x.slen + y.plen);
    if (x.slen == x.len) z.plen = x.len + y.plen;
    if (y.plen == y.len) z.slen = x.slen + y.len;
  }
  return z;
}

S e() { return {0, 0, 0, 0, 0, 0}; }

A small but important detail is the following:

  if (x.len == 0) return y;
  if (y.len == 0) return x;

In other problems, we could define \(f(\lbrace \rbrace)\) appropriately for the empty sequence \(\lbrace \rbrace\). In this problem, however, whatever definition we choose for \(f(\lbrace \rbrace)\), it is difficult to make

\[\mathrm{op}(f(X), f(\lbrace \rbrace)) = \mathrm{op}(f(\lbrace \rbrace), f(X)) = f(X)\]

hold naturally.

In such a case, a simple approach is to assign a suitable element as the identity and return the other operand whenever one of \(f(X),f(Y)\) is the identity. The two lines above implement this approach.

Be careful that the operation can fail if some nonempty sequence \(X\) can have \(f(X)\) equal to the identity.

Implementing the ideas explained above solves the problem. The time complexity is \(\mathrm{O}(N + Q \log N)\), which is sufficiently fast.

• Sample implementation, C++