P10880 [JRKSJ R9] Mo's Algorithm 1.5-Approximate Construction

The construction of 2D Mo's algorithm can be seen as a TSP problem on a complete graph where the edge weight between $i, j$ is $|l_i-l_j|+|r_i-r_j|$. Clearly, the edge weights of any Mo ordering satisfy the triangle inequality. Compute the minimum spanning tree, then take all vertices with odd degree, and run a minimum-weight matching on the induced subgraph to obtain $E$. Add $E$ to the minimum spanning tree, and then find an Euler tour. Note that $\text{MST}(S)\le \text{TSP}(S)$, $2E\le \text{TSP}(S)$ (a $\text{TSP}$ solution for $E$ can give two matchings; consider the smaller one), and the total edge weight of the Euler tour is no less than the weight of the solution given by the Euler tour, which yields a result $\le 1.5\text{TSP}(S)$.

You are given a permutation $a$ of $1 \sim n$ and $m$ intervals $[l_i, r_i]$ on this permutation. For a value-domain interval $[L, R]$: - Define the “value of this value-domain interval when choosing $i$” as how many numbers in $a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$ belong to the value-domain interval $[L, R]$. - Define the value of the value-domain interval $[L, R]$ as the maximum of the above quantity over all $\forall i \in [1, m]$. That is, the value of the value-domain interval $[L, R]$ is $\displaystyle\max_{i=1}^m \sum_{j=l_i}^{r_i} [L\le a_j\le R]$. Two intervals are defined to intersect if and only if there exists at least one integer contained in both intervals. Please choose several **pairwise non-intersecting** value-domain intervals such that the product of their values is maximized. Output this answer modulo $998244353$.

The first line contains two integers $n, m$. The second line contains $n$ integers denoting $a_{1 \dots n}$. The next $m$ lines each contain two integers $l_i, r_i$.

Output one integer denoting the answer. Output the answer modulo $998244353$.

### Sample Explanation 1 Choose the value-domain interval $[1,3]$. ### Sample Explanation 2 You can choose the value-domain intervals $[1,3], [4,5], [8,10]$. ### Sample Explanation 3 Sample 3 satisfies the special property. ### Constraints and Notes **This problem uses bundled testdata.** | $\mathrm{Subtask}$ | $n,m\le$ | Special property | Score | | :-----: | :-----: | :-----: | :-----: | | $1$ | $20$ | | $10$ | | $2$ | $5\times 10^3$ | | $15$ | | $3$ | $3\times 10^5$ | $\checkmark$ | $10$ | | $4$ | $5\times 10^4$ | | $25$ | | $5$ | $3\times 10^5$ | | $40$ | Special property: it is guaranteed that $\forall i\in[1,n], a_i=i$. For all testdata, it is guaranteed that $1\le n,m\le 3\times 10^5$, $1\le l_i\le r_i\le n$, and $a$ is a permutation of $1\sim n$. Translated by ChatGPT 5