题目背景

$\text{upd2021.8.16}$：增加两组 hack 数据，并缩小时限至 1.2s。

题目描述

给你一个长度为 $n$ 的 $01$ 序列 $a$，$m$ 次询问，支持 $2$ 种询问：

• 1 l r 表示询问 $l$ 到 $r$ 区间的最长不下降子序列的长度。
• 2 l r 表示询问 $l$ 到 $r$ 区间的最长上升子序列的长度。

输入格式

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

输出格式

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

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

5
2
2
1

提示

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le m\le 5\times10^6$，$0\le a_i\le 1$。

本题输入输出量极大，这里给出出题人使用的快读快写。（当然，使用您自己编写的大概率也能通过）

namespace IO{//by cyffff
	int len=0;
	char ibuf[(1<<20)+1],*iS,*iT,out[(1<<26)+1];
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
	#define reg register
	inline int read(){
		reg char ch=gh();
		reg int x=0;
		reg char t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
	inline void putc(char ch){
		out[len++]=ch;
	}
	template<class T>
	inline void write(T x){
		if(x<0)putc('-'),x=-x;
		if(x>9)write(x/10);
		out[len++]=x%10+48;
	}
	inline void flush(){
		fwrite(out,1,len,stdout);
		len=0;
	}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::putc;

使用这种快读快写读入一个数 $x$ 时请使用语句 x=read();，输出时使用语句 write(x);。注意，换行时需使用语句 putc('\n');，程序执行结束时使用语句 flush();。

在使用此快读时请加上 #include<bits/stdc++.h>。

如果本地无法输入，可以尝试使用 这里的快读快写。

若仍看不懂，请在赛时答疑帖回复/私信出题人。

由于出题人只会 C++，本处无法给出其他语言的快读快写，深感歉意。

样例解释:

对于第一个询问，满足的序列有：$\{0,1,1,1,1\},\{0,0,0,0,1\}$。
对于第二个询问，满足的序列有：$\{0,1\}$。
对于第三个询问，满足的序列有：$\{0,0\},\{0,1\},\{1,1\}$。
对于第四个询问，满足的序列有：$\{0\},\{1\}$。

本题时限、空限保证为出题人所用的两倍以上。
如果您仍认为卡常，则请私信出题人或者发帖并 @ 出题人。