经典树状数组/线段树思想学习——[SDOI2009]HH的项链/NOI.ac#44. color

HH的项链

#include<cstdio>
#include<vector>

inline void input(int &x){
    int ans=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        ans=(ans<<1)+(ans<<3)+(c-48);
        c=getchar();
    }
    x=ans*f;
}

inline void output(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)output(x/10);
    putchar(x%10+48);
}

inline void writeln(int x){
    output(x);
    putchar('\n');
}

int n,m,c[1000005],a[1000005],left[1000005],right[1000005],
    last[1000005],out[1000005],now[1000005];

std::vector<int> zhi[1000005];

inline int lowbit(int x){
    return x&(-x);
}

inline void add(int now,int x){
    while(now<=n){
        c[now]+=x;
        now+=lowbit(now);
    }
}

inline int sum(int now){
    int ans=0;
    while(now){
        ans+=c[now];
        now-=lowbit(now);
    }
    return ans;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        last[i]=now[a[i]];
        now[a[i]]=i;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&left[i],&right[i]);
        zhi[right[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        if(last[i])add(last[i],-1);
        add(i,1);
        for(int j=0;j<zhi[i].size();j++){
            out[zhi[i][j]]=sum(right[zhi[i][j]])-sum(left[zhi[i][j]]-1);
        //  printf("%d %d\n",zhi[i][j],out[zhi[i][j]]);
        }
    }
    for(int i=1;i<=m;i++){
        printf("%d\n",out[i]);
    }
}

进阶：屠龙宝刀点击就送

#include<cstdio>
#include<algorithm>

int n,m,k,t,a[500005],tot[500005],id[500005],now[500005],
    nex[500005],last[500005],fir[500005],ans[500005],fa[500005];

struct BIT{
    int C[500005];
    inline int lowbit(int X){return X&(-X);}
    inline void add(int K,int X){
        while(K<=n){
            C[K]+=X;
            K+=lowbit(K);
        }
    }
    inline int query(int K){
        int ANS=0;
        while(K){
            ANS+=C[K];
            K-=lowbit(K);
        }
        return ANS;
    }
}T;

struct ask{
    int id,l,r;
}e[500005];

inline bool cmp(ask x,ask y){return x.r<y.r;}

int main(){
    scanf("%d%d%d%d",&n,&m,&k,&t);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        tot[a[i]]++;
        id[i]=tot[a[i]];
        nex[last[a[i]]]=i;
        fa[i]=last[a[i]];
        last[a[i]]=i;
        if(!fir[a[i]])fir[a[i]]=i;
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&e[i].l,&e[i].r);
        e[i].id=i;
    }
    std::sort(e+1,e+m+1,cmp);
    for(int i=1,qvq=1;i<=n;i++){
        if(id[i]==t){
            T.add(fir[a[i]],1);
            now[a[i]]=fir[a[i]];
        }
        else if(id[i]>t){
            T.add(now[a[i]],-1);
            if(fa[now[a[i]]])T.add(fa[now[a[i]]],1);//
            T.add(nex[now[a[i]]],1);
            T.add(now[a[i]],-1);//
            now[a[i]]=nex[now[a[i]]];
        }
        while(e[qvq].r==i){
            ans[e[qvq].id]=T.query(i)-T.query(e[qvq].l-1);
        //  printf("%d %d %d %d\n",e[qvq].l,e[qvq].r,e[qvq].id,ans[e[qvq].id]);
            qvq++;
        }
    }
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}