记录编号	599533	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO21Feb Platinum]No Time to Dry	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	3.074 s
提交时间	2025-03-20 21:37:56	内存使用	16.81 MiB

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5+10;

int pre[N];

struct node{
	int a,b,id;
}qa[N];

bool cmp(node a,node b){
	return a.b<b.b;
}

int n,q,t[N],res[N],s[N];
int x[N*4];//?????????
 
void build(int u,int l,int r){
	if(l==r){
		x[u]=s[l];
		return ;
	}
	int mid=(l+r)/2;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	x[u]=min(x[u*2],x[u*2+1]);
	return ;
} 

int g_min(int u,int l,int r,int ql,int qr){
	if(l==ql&&r==qr){
		return x[u];
	}
	int mid=(l+r)/2;
	if(qr<=mid)return g_min(u*2,l,mid,ql,qr);
	if(ql>mid)return g_min(u*2+1,mid+1,r,ql,qr);
	return min(g_min(u*2,l,mid,ql,mid),g_min(u*2+1,mid+1,r,mid+1,qr));	 
} 

int sm[N*4];

void push_down(int p){
	sm[p*2]+=sm[p];
	sm[p*2+1]+=sm[p];
	sm[p]=0;
	return;
}

void insert(int p,int l,int r,int ql,int qr){
	if(l==ql&&r==qr){
		sm[p]++;
		return;
	}
	int mid=(l+r)>>1;
	if(qr<=mid)insert(p*2,l,mid,ql,qr);
	else if(ql>mid)insert(p*2+1,mid+1,r,ql,qr);
	else insert(p*2,l,mid,ql,mid),insert(p*2+1,mid+1,r,mid+1,qr);
}

int getans(int p,int l,int r,int q){
	if(l==r)return sm[p];
	push_down(p);
	int mid=(l+r)>>1;
	if(q<=mid)return getans(p*2,l,mid,q);
	return getans(p*2+1,mid+1,r,q);
}

signed main(){
	freopen("dry.in","r",stdin);
	freopen("dry.out","w",stdout);
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%lld",&s[i]);
	}
	build(1,1,n); 
	for(int i=1;i<=q;i++){
		scanf("%lld%lld",&qa[i].a,&qa[i].b);
		qa[i].id=i; 
	}
	sort(qa+1,qa+1+q,cmp);
	for(int i=1;i<=n;i++)pre[i]=t[s[i]],t[s[i]]=i;
	int now=1;
//	return 0;
	for(int i=1;i<=n;i++){
		if(s[i]<=g_min(1,1,n,pre[i]+1,i)){
			insert(1,1,n,pre[i]+1,i);
		}else{
			insert(1,1,n,1,i);
		}
		while(now<=q&&qa[now].b==i){
			res[qa[now].id]=getans(1,1,n,qa[now].a);
			now++;
		}
	} 
	for(int i=1;i<=q;i++){
		printf("%lld\n",res[i]);
	}
	return 0;
}