洛谷 P1972 HH的项链

传送门：洛谷 P1972 HH的项链
算法分析：先排序（右边界从小到大，这样就不会对答案产生影响），然后用树状数组维护从\([1,j]\)中不同的数量，最后用前缀和计算即可

#include<iostream>
#include<cstdio>
#include<algorithm>
#define in(x) x=read()
using namespace std;
const int maxN=500000;
struct Q
{
    int l,r,id;
}que[maxN+1];
int tree[maxN+1],n,m,a[maxN+1];
int ans[maxN+1],flag[maxN+1];
inline int read(),sum(int);
inline int lowbit(int x) {return x&(-x);}
void update(int,int);
bool comp(Q x,Q y) {return x.r<y.r;}
int main()
{
    in(n); for(int i=1;i<=n;i++) in(a[i]); in(m);
    for(int i=1;i<=m;i++)
    {
        in(que[i].l); in(que[i].r);
        que[i].id=i;
    }
    sort(que+1,que+m+1,comp);
    for(int i=1;i<=m;i++)
    {
        for(int j=que[i-1].r+1;j<=que[i].r;j++)
        {
            if(flag[a[j]]) update(flag[a[j]],-1);
            update(j,1); flag[a[j]]=j;
        }
        ans[que[i].id]=sum(que[i].r)-sum(que[i].l-1);
    }
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);    
    return 0;
}
void update(int x,int val) {while(x<=n) {tree[x]+=val; x+=lowbit(x);}}
inline int read()
{
    char ch=getchar();
    int num=0,f=1;
    while((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();
    if(ch==‘-‘) {f=-1; ch=getchar();}
    while(ch>=‘0‘ && ch<=‘9‘)
    {
        num=num*10+ch-‘0‘;
        ch=getchar();
    }
    return num*f;
}
inline int sum(int x)
{
    int ans=0;
    while(x) {ans+=tree[x]; x-=lowbit(x);}
    return ans;
}

洛谷 P1972 HH的项链

原文：https://www.cnblogs.com/ezsyshx/p/10358891.html