记录编号	599200	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	郑霁桓	是否通过	通过
代码语言	C++	运行时间	2.528 s
提交时间	2025-03-04 21:11:17	内存使用	13.68 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000006],m,as[1000006],pl,pr,ps,t[1000006];
struct nm{
    long long l,r,p;
}b[1000006];
bool c(nm x,nm y){
    if(x.l/1000==y.l/1000) return x.r<y.r;
    return x.l<y.l;
}
int main(){
    freopen("diff.in","r",stdin);
    freopen("diff.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    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),t[0]=1e9;
    for(int i=1;i<=m;i++){
        if(b[i-1].r<b[i].r){
            for(int j=b[i-1].r+1;j<=b[i].r;j++)
                if(t[a[j]]++==0) ps++;
        }else{
            for(int j=b[i].r+1;j<=b[i-1].r;j++)
                if(--t[a[j]]<=0) ps--;
        }
        if(b[i-1].l<b[i].l){
            for(int j=b[i-1].l;j<b[i].l;j++)
                if(--t[a[j]]<=0) ps--;
        }else{
            for(int j=b[i].l;j<b[i-1].l;j++)
                if(t[a[j]]++==0) ps++;
        }
        as[b[i].p]=ps;
    }
    for(int i=1;i<=m;i++) cout<<as[i]<<"\n";
    return 0;
}