[1] Solution 1: Add the information needed for merging

We design a monoid by adding the information needed to merge intervals. For example, we can use the following design.

For each state \((k,a,b)\), store the maximum sum of the selected elements subject to the following conditions:

• We have selected \(k\) intervals (\(1\leq k\leq 2\)).
• \(a\in \lbrace 0,1\rbrace\): Whether the leftmost element is selected.
• \(b\in \lbrace 0,1\rbrace\): Whether the rightmost element is selected.

When merging the information for intervals \(X,Y\), the flags \(a,b\) can be used to determine whether \(2\) adjacent contiguous subsequences can be joined.

In addition to these \(8\) states, an is_empty flag for handling the empty sequence, which serves as the segment tree’s identity element, makes implementation easier.

• Sample solution: https://atcoder.jp/contests/aalc001/submissions/79783903

---

[2] Solution 2: Represent dynamic programming with matrices

Consider a single answer query as dynamic programming that processes the elements of the sequence from left to right. Selecting at most \(2\) contiguous subsequences corresponds to coloring each element with one of \(5\) colors, \(0,1,2,3,4\), such that

• The colors are nondecreasing from left to right.
• Elements of colors \(1,3\) are selected.

This gives a DP with \(5\) states for a single answer query. The DP transition for processing each element can be represented by a \(5\times 5\) max-plus matrix. Storing the transition matrix for each element in a segment tree solves this problem.

Chapter 7 of “Designing Monoids for Range Queries” explains in detail how to represent DP transitions with matrices and store them in a segment tree. In particular, this problem can be viewed as an extension of the DP with 3 states in Section 7.6 to 5 states.

• Sample solution: https://atcoder.jp/contests/aalc001/submissions/79784002

---

[3] Implementation considerations when using matrices

Let the number of states be a constant \(K\), and store a \(K\times K\) matrix at each node of the segment tree. Performance can vary considerably depending on the implementation.

Storing the data

Storing a data structure such as vector<vector<long long>> at each node of the segment tree causes many dynamic memory allocations and pointer accesses. Since \(K=5\) is fixed, use a fixed-size array such as array<array<long long, K>, K> in C++.

In other languages, fixed-size arrays or flattening arrays into \(1\) dimension may also improve performance.

Using upper triangularity

All matrices in this problem are upper triangular. This corresponds to the fact that, in the DP state design above, a transition from state \(i\) to state \(j\) is possible only when \(i\leq j\).

Therefore, when computing the matrix product \(z=xy\), we can reduce the number of operations by using the following loops:

• General matrix product: For \(0\leq a,b,c < K\), use \(x[a][b]\) and \(y[b][c]\) to update \(z[a][c]\).
• Upper triangular matrix product: For \(0\leq a\leq b\leq c < K\), use \(x[a][b]\) and \(y[b][c]\) to update \(z[a][c]\).

For example, when \(K=5\), the number of loop iterations decreases from \(125\) to \(35\).

How much this reduces the actual running time depends on \(K\), the programming language, and the cost of the operations performed on matrix entries.

This problem also has other properties, such as trivial diagonal entries and entries that are always equal, that can further reduce the number of operations. Among such optimizations, upper triangularity is useful in many situations and easy to use, so it is recommended.

Storing only the upper triangular entries also reduces the memory needed for the matrices. However, this makes indexing somewhat more complicated, so we do not discuss it here.