题意分析
题目部分
本题核心：如何判断一个区间内的贝壳是否重复？
当右端点 \(r\) 固定时，不论 \(l\) 取何值，对于任意一组重复的贝壳，都可以只统计最右端的贝壳。
原因：设一组重复贝壳中最右端的贝壳所在的位置为 \(pos_r\)，那么当 \(pos_r < l\) 时，其他贝壳也不可能算进统计中，当 $pos_r \ge l $时，无论其他贝壳是否被包括，对于区间的贡献都只有 \(1\)，因此，只计算最右端的贝壳即可。
因此，只需要将所有询问区间按 \(r\) 从小到大排序，计算答案即可。
通过树状数组操作
以位置为下标，每遇到一个新的数 \(num(num \le r)\)，判断它是否重复，如果重复，那么将上一个相同的数的贡献值 \(-1\)，将当前数的贡献值 \(+1\)。
对于一段区间 \([l,r]\)，答案为 \(sum(r)-sum(l-1)\)。
code
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,ask_r,prev,pos;
int vis[1000005],a[1000005],t[1000005],ans[1000005];
struct A{
int l,r,num;
}ask[1000005];
bool cmp(A x,A y){
return x.r<y.r;
}
int find(int pos){
ask_r=ask[pos++].r;
while(ask_r==ask[pos].r) pos++;
return pos-1;
}
void add(int x,int y){
for(;x<=n;x+=(x&-x)) t[x]+=y;
return;
}
int sum(int x){
int su=0;
for(;x;x-=(x&-x)) su+=t[x];
return su;
}
void replace(){
for(int i=ask[prev].r+1;i<=ask_r;i++){
if(vis[a[i]]!=0) add(vis[a[i]],-1);
add(i,1);
vis[a[i]]=i;
}
for(int i=prev+1;i<=pos;i++) ans[ask[i].num]=sum(ask[i].r)-sum(ask[i].l-1);
return;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++) scanf("%d%d",&ask[i].l,&ask[i].r),ask[i].num=i;
sort(ask+1,ask+m+1,cmp);
while(1){
if(pos==m) break;
prev=pos;
pos=find(pos+1);
replace();
}
for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
return 0;
}