bzoj2743 [HEOI2012]采花——树状数组+离线

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2743

和 HH的项链 那道题很像，也是类似的做法；

但不同的是这里的点只有有前驱时才起作用；

自己的思路还是不清晰，总想着遍历到的这个点如何如何...

其实跟这个点无关，只关注它的前驱，给前驱 +1，这个1就表示前驱和自己同时存在；

那么前驱的前驱 -1，因为它对现在的这个点已经没用了，而它曾经被 +1 过。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const maxn=1e6+;

int n,c,m,f[maxn],a[maxn],lst[maxn],prt[maxn];

struct Q{int l,r,w,bh;}q[maxn];

int rd()

{

    int ret=;char ch=getchar();

    while(ch<''||ch>'')ch=getchar();

    while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

    return ret;

}

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

bool cmp2(Q x,Q y){return x.bh<y.bh;}

void add(int x,int k)

{

    for(;x<=n;x+=(x&-x))f[x]+=k;

}

int query(int x)

{

    int ret=;

    for(;x;x-=(x&-x))ret+=f[x];

    return ret;

}

int main()

{

    n=rd(); c=rd(); m=rd();

    for(int i=;i<=n;i++)a[i]=rd();

    for(int i=;i<=m;i++)q[i].l=rd(),q[i].r=rd(),q[i].bh=i;

    sort(q+,q+m+,cmp);

    int tot=;

    for(int i=;i<=n;i++)

    {

        if(!lst[a[i]]&&!prt[a[i]])lst[a[i]]=i;

        else if(!prt[a[i]])

        {

            prt[a[i]]=lst[a[i]]; lst[a[i]]=i;

            add(prt[a[i]],);

//            add(i,1);

        }

        else

        {

            add(prt[a[i]],-);

            prt[a[i]]=lst[a[i]]; lst[a[i]]=i;

            add(prt[a[i]],);//

//            add(i,1);

        }

//        printf("prt[%d]=%d lst[%d]=%d\n",a[i],prt[a[i]],a[i],lst[a[i]]);

//        while(q[tot].r==i)q[tot].w=(query(i)-2*query(q[tot].l-1))/2,tot++;

        while(q[tot].r==i)q[tot].w=query(i)-query(q[tot].l-),tot++;

    }

    sort(q+,q+m+,cmp2);

    for(int i=;i<=m;i++)printf("%d\n",q[i].w);

    return ;

}