P7809 [JRKSJ R2] 01 序列

给你一个长度为 $n$ 的 $01$ 序列 $a_{1\sim n}$，接下来有两种询问共 $m$ 次： - `1 l r`，表示询问 $l$ 到 $r$ 区间的最长不下降子序列的长度。 - `2 l r`，表示询问 $l$ 到 $r$ 区间的最长上升子序列的长度。

输入 $m+2$ 行。\ 第 $1$ 行两个正整数 $n,m$。\ 第 $2$ 行 $n$ 个数字 $0$ 或 $1$ 代表序列 $a_{1\sim n}$。\ 接下来 $m$ 行每行三个正整数表示一次询问，格式如上。

输出 $m$ 行。\ 对于每一次询问求出答案并输出。

本题采用捆绑测试。 | $\text{Subtask}$ | $n\le$ | $m\le$ | 特殊性质 | 分值 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $\text{1}$ | $10^6$ | $10^6$ | 所有 $a_i$ 均相等 | $5$ | | $\text{2}$ | $10^3$ | $10^3$ | 无 | $10$ | | $\text{3}$ | $10^4$ | $10^4$ | 无 | $15$ | | $\text{4}$ | $10^5$ | $10^5$ | 无 | $30$ | | $\text{5}$ | $10^6$ | $5\times10^6$ | 无 | $40$ | | $\text{6}$ | $10^6$ | $5\times10^6$ | hack 数据 | $0$ | 对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le m\le 5\times10^6$，$0\le a_i\le 1$。 本题输入输出量极大，请使用较为快速的输入输出方法。 #### 样例解释: 对于第一个询问，满足的序列有：$\{0,1,1,1,1\},\{0,0,0,0,1\}$。\ 对于第二个询问，满足的序列有：$\{0,1\}$。\ 对于第三个询问，满足的序列有：$\{0,0\},\{0,1\},\{1,1\}$。\ 对于第四个询问，满足的序列有：$\{0\},\{1\}$。 $\text{Upd 2021.8.16}$：增加两组 Hack 数据。