记录编号	599355	评测结果	AAAAAAAAAA
题目名称	[HEOI 2012]采花	最终得分	100
用户昵称	彭欣越	是否通过	通过
代码语言	C++	运行时间	5.281 s
提交时间	2025-03-08 15:29:53	内存使用	13.84 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2000010;
int n,c,m,t[N],r[N],c1[N];
int s1[N],s2[N];
struct node {
    int l,r,id;
}a[N];
bool cmp (node x,node y) {
    return x.r<y.r;
}
int lowbit (int x) {
    return x&-x;
}
void add (int x,int v) {
	while (x<=n) {
		c1[x]+=v;
		x+=lowbit(x);
	}
} 
int query (int x) {
	int cnt=0;
	while (x>0) {
		cnt+=c1[x];
		x-=lowbit(x);
	}
	return cnt;
}
int main(){
	freopen("1flower.in","r",stdin);
    freopen("1flower.out","w",stdout);
    cin >> n >> c >> m;
    for (int i=1;i<=n;i++) cin >> t[i];
    for (int i=1;i<=m;i++) {
        cin >> a[i].l >> a[i].r;
        a[i].id=i;
    }
    sort(a+1,a+m+1,cmp);
    int j=1;
    for (int i=1;i<=m;i++) {
        for (;j<=a[i].r;j++) {
            if (!s1[t[j]]) s1[t[j]]=j;
            else {
                if (!s2[t[j]]) {
                    add(s1[t[j]],1);
                    s2[t[j]]=j;
                }else{
				    add(s2[t[j]],1);
                    add(s1[t[j]],-1);
                    s1[t[j]]=s2[t[j]];
                    s2[t[j]]=j;
                }
            }
        }
        r[a[i].id]=query(a[i].r)-query(a[i].l-1);
    }
    for (int i=1;i<=m;i++) cout << r[i] <<"\n";
	return 0;
}