HH的项链

题目来源 HH的项链-洛谷

思路 一道树状数组模板题，详细见代码注释 =)

传送门

树状数组-百度百科

树状数组详解-CSDN

代码

#include<iostream>
#include<algorithm>
#define N 1000001
using namespace std;
int a[N],tree[N],flag[N],ans[N],n,m,pos=1;
struct t{
    int l,r,pl;
}q[N];
int lowbit(int num) {
    return num&(-num);
}
void Add(int num,int point){
    while(num<=n){
        tree[num]+=point;
        num+=lowbit(num);
    }
}
int Sum(int num){
    int sum=0;
    while(num!=0){
        sum+=tree[num];
        num-=lowbit(num);
    }
    return sum;
}
bool cmp(t A,t B){
    return A.r<B.r;
}
int main(){
    ios::sync_with_stdio(0); 
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>q[i].l>>q[i].r;
        q[i].pl=i;
    }
    sort(q+1,q+m+1,cmp);
    for(int i=1;i<=m;i++){
        for(int j=pos;j<=q[i].r;j++){
            if(flag[a[j]]) Add(flag[a[j]],-1);
            Add(j,1);
            flag[a[j]]=j;
        }
        pos=q[i].r+1;
        ans[q[i].pl]=Sum(q[i].r)-Sum(q[i].l-1);
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}