记录编号	599523	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO21Feb Platinum]No Time to Dry	最终得分	100
用户昵称	郑霁桓	是否通过	通过
代码语言	C++	运行时间	2.569 s
提交时间	2025-03-20 20:57:24	内存使用	31.01 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[200005],st[20][200005],f[200005],a2,as[200005],pr[200005],ed[200005];
void ad(long long x,long long y){
    for(;x<=n;x+=(x&(-x))) f[x]+=y; 
    return;
}
long long q(long long x){
    long long s=0;
    for(;x;x-=(x&(-x))) s+=f[x];
    return s;
}
struct nm{
    long long l,r,p;
}b[200005];
bool C(nm xx,nm yy){
    return xx.r<yy.r; 
}
int main(){
    freopen("dry.in","r",stdin);
    freopen("dry.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],st[0][i]=a[i];
    for(int i=1;i<=n;i++) pr[i]=ed[a[i]],ed[a[i]]=i;
    for(int i=1;i<20;i++)
        for(int j=1;j+(1<<i)<=n;j++)
            st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]);
    for(int i=1;i<=m;i++) cin>>b[i].l>>b[i].r,b[i].p=i;
    sort(b+1,b+m+1,C);
    for(int i=1,t=1;i<=n;i++){
        a2=log2(i-pr[i]);
        if(a[i]<=min(st[a2][i-(1<<a2)],st[a2][pr[i]])) ad(pr[i]+1,1);
        else ad(1,1);
        ad(i+1,-1);
        while(b[t].r==i) as[b[t].p]=q(b[t].l),++t;
    }
    for(int i=1;i<=m;i++) cout<<as[i]<<"\n";
    return 0; 
}