Description：

给一个数列，多次询问每次从区间中取出一个严格上升的序列，然后问最少取几次。

$1\leqslant n\leqslant 2\times 10^5$

Solution：

发现其实答案就是区间众数，于是用莫队， $cnt[i]$ 表示数字 $i$ 出现了几次，但是只用这样一个是不能维护的，还要维护一个 $num[k]$ 表示 $cnt[i]$ 为 $k$ 的个数，这样减的时候只要判断 $num[cnt[i]]$ ，如果还不为零，那么答案不变。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 200010

int v[MAXN],b[MAXN];

int cnt[MAXN],num[MAXN];

int ans = 0;

struct query

{

	int l,r,id,ans;

}q[MAXN];

int pos[MAXN];

bool cmp(query a,query b){return (pos[a.l] == pos[b.l] ? a.r < b.r : a.l < b.l);}

bool cmp_id(query a,query b){return a.id < b.id;}

void add(int v)

{

	--num[cnt[v]];

	++cnt[v];

	++num[cnt[v]];

	if(cnt[v] > ans)ans = cnt[v];

	return;

}

void rem(int v)

{

	--num[cnt[v]];

	--cnt[v];

	++num[cnt[v]];

	while(num[ans] == 0)--ans;

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&v[i]);

	for(int i = 1;i <= n;++i)b[i] = v[i];

	sort(b + 1,b + 1 + n);

	b[0] = unique(b + 1,b + 1 + n) - b - 1;

	for(int i = 1;i <= n;++i)v[i] = lower_bound(b + 1,b + 1 + b[0],v[i]) - b;

	int blo = sqrt(n);

	for(int i = 1;i <= n;++i)pos[i] = (i - 1) / blo + 1;

	for(int i = 1;i <= m;++i)scanf("%d%d",&q[i].l,&q[i].r);

	for(int i = 1;i <= m;++i)q[i].id = i;

	sort(q + 1,q + 1 + m,cmp);

	for(int i = 1,l = 1,r = 0;i <= m;++i)

	{

		while(r < q[i].r)add(v[++r]);

		while(l > q[i].l)add(v[--l]);

		while(r > q[i].r)rem(v[r--]);

		while(l < q[i].l)rem(v[l++]);

		q[i].ans = ans;

	}

	sort(q + 1,q + 1 + m,cmp_id);

	for(int i = 1;i <= m;++i)printf("%d\n",-q[i].ans);

	return 0;

}