P1972 [SDOI2009] HH的项链
我们考虑将所有询问按照右端点归类。
然后从左往右扫描每个位置，如果前面有位置和它重复，就把前面的位置删掉（这样做是对的，因为右端点只可能在之后了，那么要访问到前面的位置，就必须要到达这个位置，相当于把重复的贡献减掉）。
初始时假设所有位置都不重复，都是 \(1\)。
每次操作只可能将某个位置减少 \(1\)，或者区间查询。
可以使用树状数组。
而且建树也可以直接将 \(c_i\leftarrow \text{lowbit}(c_i)\)，做到 \(O(n)\) 建树。
复杂度 \(O(n+m)\log n\)（线段树常数大）。
// Problem: P1972 [SDOI2009] HH的项链
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1972
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<cstring>
#include<cstdio>
const int N=1000010,M=4*N;
char num[10];
int cnt,c[N],n,a[N],h[N],e[N],ne[N],idx,ans[N],id[N],p[N];
void add(int a,int b,int c){
e[idx]=b,id[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void read(int &x){
x=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){
x=x*10+c-48;
c=getchar();
}
}
void write(int x){
int cur=0;
while(x)num[cur++]=x%10+'0',x/=10;
while(cur--)putchar(num[cur]);
putchar('\n');
}
void sub(int x){
for(;x<=n;x+=x&-x)--c[x];
}
int sum(int x){
int res=0;
for(;x;x-=x&-x)res+=c[x];
return res;
}
int main(){
read(n);
memset(h+1,-1,n*4);
for(int i=1;i<=n;++i)read(a[i]);
int m;
read(m);
for(int i=1;i<=m;++i){
int l,r;
read(l),read(r);
add(r,l,i);
}
for(int i=1;i<=n;++i)c[i]=i&-i;
for(int i=1;i<=n;++i){
int x=a[i];
if(p[x])sub(p[x]);
p[x]=i;
for(int j=h[i];~j;j=ne[j])ans[id[j]]=sum(i)-sum(e[j]-1);
}
for(int i=1;i<=m;++i)write(ans[i]);
return 0;
}