← 返回题单

题单练习 ST表

← 上一题下一题 →

A6889 | $01 序列$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给你一个长度为 $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$ 行。\ 对于每一次询问求出答案并输出。

输入输出样例

输入 #1

8 4
0 1 1 0 1 0 0 1
1 1 8
2 1 8
1 3 6
2 5 6

输出 #1

C++ 编辑器

输入

输出