[HEOI2012]采花

一道神仙题。

传送门

题意

求区间中出现两次的颜色的个数，卡莫队。

做法

这题是HH的项链那题的变形吧，但那题我用莫队水过去了，于是到这题就自闭了。

首先做法是离线，将询问以l为第一关键字,r为第二关键字排序，这样我们得到一个l有序的询问序列。

对于每种颜色，预处理出它第一次出现的位置$p[i]$和每个位置后一个位置$nx[i]$。

用一个l指针从左往右扫，用树状数组维护前缀和，使l后每个颜色的第二个出现位置上的值为一，之后就是求$[l,r]$的和。

具体实现代码如下：

for (int i=1; i<=m; i++){
        for (int j=next; j<q[i].l; j++){
            if (nx[j]) add(nx[j],-1);
            if (nx[j]&&nx[nx[j]]) add(nx[nx[j]],1);
        }
        next=q[i].l;
        num[q[i].h]=query(q[i].r)-query(q[i].l-1);
    }

我觉得我讲的并不太易懂，所以带大家来看一组样例。

感觉我这个样例十分垃圾

由于我太菜了做不出动态图，所以大家可以无视我的箭头和指针单玩样例。

完整代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int l,r,h;
}q[2000001];
int a[2000010],nx[2000001],p[2000001];
int next=1,num[2000001],n,m,k,c[2000001];
inline bool cmp(node c,node d){return c.l!=d.l?c.l<d.l:c.r<d.r;}
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int y){while(x<=n) c[x]+=y,x+=lowbit(x);}
inline int query(int x){int ans=0;while(x)ans+=c[x],x-=lowbit(x);return ans;}
int main(){
    scanf("%d%d%d",&n,&k,&m);
    for (int i=1; i<=n; i++) scanf("%d",&a[i]);
    for (int i=n; i>=1; i--) nx[i]=p[a[i]],p[a[i]]=i;
    for (int i=1; i<=k; i++) if (p[i]&&nx[p[i]]) add(nx[p[i]],1);
    for (int i=1; i<=m; i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].h=i;
    }
    sort(q+1,q+m+1,cmp);
    for (int i=1; i<=m; i++){
        for (int j=next; j<q[i].l; j++){
            if (nx[j]) add(nx[j],-1);
            if (nx[j]&&nx[nx[j]]) add(nx[nx[j]],1);
        }
        next=q[i].l;
        num[q[i].h]=query(q[i].r)-query(q[i].l-1);
    }
    for (int i=1; i<=m; i++) printf("%d\n",num[i]);
    return 0;
}