BZOJ-2743: [HEOI2012]采花

Description

给出m次询问，每次询问[l,r]区间，该种颜色出现次数大于2的颜色个数。

离线+树状数组。
我们发现当右端点固定的时候左端点只要满足小于每种从后往前数的第2个就对答案有一点贡献。所以将询问离线，按照右端点排序，在处理询问的时候不断修改第二个节点的位置，树状数组维护一下。

加点的复杂度O(nlogn)，查询的复杂度O(mlogn)，询问排序复杂度O(mlogm)。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1001000
int n,m,c,atf[N],bef[N],f[N],col[N];
struct quest
{
    int l,r,id,ans;
}q[N];
inline bool cmp1(const quest x,const quest y) {return x.r<y.r;}
inline bool cmp2(const quest x,const quest y) {return x.id<y.id;}
void fix(int x,int w)
{
    for(;x>0;x-=-x&x) f[x]+=w;
}
int query(int x,int y)
{
    int re=0;
    for(;x<=y;x+=-x&x) re+=f[x];
    return re;
}
int main()
{
    scanf("%d%d%d",&n,&c,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&col[i]);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+m+1,cmp1);
    int now=0;
    for(int i=1;i<=m;i++)
    {
        while(q[i].r>now)
        {
            now++; 
            if(atf[col[now]])
            {
                fix(atf[col[now]],-1);
                fix(bef[col[now]],1);
                atf[col[now]]=bef[col[now]];
                bef[col[now]]=now;
            }
            else
            {
                if(bef[col[now]])
                {
                    fix(bef[col[now]],1);
                    atf[col[now]]=bef[col[now]];
                    bef[col[now]]=now;
                }
                else bef[col[now]]=now;
            }

        }
        q[i].ans=query(q[i].l,q[i].r);
    }
    sort(q+1,q+m+1,cmp2);
    for(int i=1;i<=m;i++)
        printf("%d\n",q[i].ans);
    return 0;
}