BZOJ 2743 [HEOI2012]采花 离线+线段树

题意:
c种颜色，多次询问一段区间出现不少于两次的颜色个数。
解析:
和HH的项链差不多的题。
HH的项链我记得是求什么上一次出现位置小于l的个数。
这题的处理方法类似，如没做过HH，则推荐先去做HH。
首先离线所有询问，之后按照右端点排序，动态加点。
每加一个点，相当于pre[pre[i]]+1~pre[i]这一段的贡献增加1，直接上线段树区间修改即可。
至于询问，显然是询问当前的l位置的权值。
所以这是个单点查询…
代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1000100
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
int n,c,m;
int col[N],last[N],pre[N];
int sum[N<<2],cov[N<<2];
int ans[N];
void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];    
}
void pushdown(int rt,int l,int r)
{
    if(cov[rt])
    {
        int mid=(l+r)>>1;
        sum[rt<<1]+=cov[rt]*(mid-l+1);
        sum[rt<<1|1]+=cov[rt]*(r-mid);
        cov[rt<<1]+=cov[rt];
        cov[rt<<1|1]+=cov[rt];
        cov[rt]=0;
    }
}
void update(int v,int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        cov[rt]+=v;
        sum[rt]+=v*(r-l+1);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(rt,l,r);
    if(L<=mid)update(v,L,R,lson);
    if(R>mid)update(v,L,R,rson);
    pushup(rt);
}
int que(int p,int l,int r,int rt)
{
    if(l==r)
    {
        return sum[rt];
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if(p<=mid)return que(p,lson);
    else return que(p,rson);
}
struct Query
{
    int l,r,no;
    friend istream& operator >> (istream &_,Query &a)
    {scanf("%d%d",&a.l,&a.r);return _;}
}query[N];
bool cmp(Query a,Query b)
{
    return a.r<b.r;
}
int main()
{
    scanf("%d%d%d",&n,&c,&m);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        if(last[x]!=0)
            pre[i]=last[x];
        last[x]=i;
        col[i]=x;
    } 
    for(int i=1;i<=m;i++)
        cin>>query[i],query[i].no=i;
    sort(query+1,query+m+1,cmp);
    int la=0;
    for(int i=1;i<=m;i++)
    {
        int l=query[i].l,r=query[i].r;
        for(int j=la+1;j<=r;j++)
        {
            if(pre[pre[j]]+1<=pre[j])
                update(1,pre[pre[j]]+1,pre[j],1,n,1);
        }
        ans[query[i].no]=que(l,1,n,1);
        la=r;
    }
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}