记录编号	599352	评测结果	AAAAAAAATT
题目名称	[HEOI 2012]采花	最终得分	80
用户昵称	郑霁桓	是否通过	未通过
代码语言	C++	运行时间	25.149 s
提交时间	2025-03-08 15:24:16	内存使用	20.21 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000006],m,k,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("1flower.in","r",stdin);
    freopen("1flower.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    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++){
        while(b[i].l<b[i-1].l) if(t[a[--b[i-1].l]]++==1) ps++;
        while(b[i].r>b[i-1].r) if(t[a[++b[i-1].r]]++==1) ps++;
        while(b[i].l>b[i-1].l) if(--t[a[b[i-1].l++]]==1) ps--;
        while(b[i].r<b[i-1].r) if(--t[a[b[i-1].r--]]==1) ps--;
        as[b[i].p]=ps;
    }
    for(int i=1;i<=m;i++) cout<<as[i]<<"\n";
    return 0;
}