A6889. 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$ 行每行三个正整数表示一次询问，格式如上。
第 $1$ 行两个正整数 $n,m$。\
第 $2$ 行 $n$ 个数字 $0$ 或 $1$ 代表序列 $a_{1\sim n}$。\
接下来 $m$ 行每行三个正整数表示一次询问，格式如上。
输出格式
输出 $m$ 行。\
对于每一次询问求出答案并输出。
对于每一次询问求出答案并输出。
输入输出样例
输入 #1
8 4 0 1 1 0 1 0 0 1 1 1 8 2 1 8 1 3 6 2 5 6
输出 #1
5 2 2 1
说明/提示
对于 $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\}$。
#### 样例解释:
对于第一个询问，满足的序列有：$\{0,1,1,1,1\},\{0,0,0,0,1\}$。\
对于第二个询问，满足的序列有：$\{0,1\}$。\
对于第三个询问，满足的序列有：$\{0,0\},\{0,1\},\{1,1\}$。\
对于第四个询问，满足的序列有：$\{0\},\{1\}$。