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

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int S=450;
int n,Q,a[N],ans[N];
int L[N],R[N],pre[N];
struct qnode{
	int l,r,x,q;
}que[N];
bool cmp(qnode a,qnode b){
	if(a.x==b.x)return a.r<b.r;
	return a.x<b.x;
}
int t[N];
void pushup(int p){
	t[p]=min(t[p<<1],t[p<<1|1]);
}
void build(int p,int l,int r){
	if(l==r){
		t[p]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	pushup(p);
}
int query(int p,int l,int r,int L,int R){
	if(L>R)return -1;
	if(L<=l&&r<=R){
		return t[p];
	}
	int mid=(l+r)>>1;
	if(R<=mid) return query(p<<1,l,mid,L,R);
	if(L>mid) return query(p<<1|1,mid+1,r,L,R);
	return min(query(p<<1,l,mid,L,R),query(p<<1|1,mid+1,r,L,R));
}
int main(){
	freopen("dry.in","r",stdin);
	freopen("dry.out","w",stdout);
	std::cin>>n>>Q;
	for(int i=1;i<=n;i++) std::cin>>a[i];
	build(1,1,n);
	memset(pre,0,sizeof(pre));
	for(int i=1;i<=n;i++){
		if(pre[a[i]]) L[i]=(query(1,1,n,pre[a[i]],i)<a[i]?-1:pre[a[i]]);
		else L[i]=-1;pre[a[i]]=i;
	}
	memset(pre,0,sizeof(pre));
	for(int i=n;i;i--){
		if(pre[a[i]]) R[i]=(query(1,1,n,i,pre[a[i]])<a[i]?n+5:pre[a[i]]);
		else R[i]=n+5;pre[a[i]]=i;
	}
	for(int i=1;i<=Q;i++){
		int l,r;
		std::cin>>l>>r;
		que[i]=(qnode){l,r,l/S+1,i};
	}
	sort(que+1,que+Q+1,cmp);
	int l=1,r=0,res=0;
	for(int i=1;i<=Q;i++){
		int ql=que[i].l,qr=que[i].r;
		while(l>ql){
			l--;
			res+=R[l]>r;
		}
		while(r<qr){
			r++;
			res+=L[r]<l;
		}
		while(l<ql){
			res-=R[l]>r;
			l++;
		}
		while(r>qr){
			res-=L[r]<l;
			r--;
		}
		ans[que[i].q]=res;
	}
	for(int i=1;i<=Q;i++) std::cout<<ans[i]<<endl;
	return 0;
}