P7809 [JRKSJ R2] 01 Sequence

You are given a $01$ sequence $a_{1\sim n}$ of length $n$. Then there are $m$ queries of two types: - `1 l r`: query the length of the longest non-decreasing subsequence in the interval from $l$ to $r$. - `2 l r`: query the length of the longest increasing subsequence in the interval from $l$ to $r$.

The input contains $m+2$ lines.\ Line $1$ contains two positive integers $n, m$.\ Line $2$ contains $n$ numbers $0$ or $1$, representing the sequence $a_{1\sim n}$.\ The next $m$ lines each contain three positive integers describing one query, in the format above.

Output $m$ lines.\ For each query, compute the answer and output it.

This problem uses bundled testdata. | $\text{Subtask}$ | $n\le$ | $m\le$ | Special Property | Score | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $\text{1}$ | $10^6$ | $10^6$ | All $a_i$ are equal | $5$ | | $\text{2}$ | $10^3$ | $10^3$ | None | $10$ | | $\text{3}$ | $10^4$ | $10^4$ | None | $15$ | | $\text{4}$ | $10^5$ | $10^5$ | None | $30$ | | $\text{5}$ | $10^6$ | $5\times10^6$ | None | $40$ | | $\text{6}$ | $10^6$ | $5\times10^6$ | hack testdata | $0$ | For $100\%$ of the testdata, $1\le n\le 10^6$, $1\le m\le 5\times10^6$, and $0\le a_i\le 1$. The input and output size is extremely large, so please use fast I/O methods. #### Sample Explanation: For the first query, valid sequences include $\{0,1,1,1,1\}$ and $\{0,0,0,0,1\}$.\ For the second query, valid sequences include $\{0,1\}$.\ For the third query, valid sequences include $\{0,0\}$, $\{0,1\}$, and $\{1,1\}$.\ For the fourth query, valid sequences include $\{0\}$ and $\{1\}$. $\text{Upd 2021.8.16}$: Added two sets of hack testdata. Translated by ChatGPT 5