洛谷4113 [HEOI2012]采花

题意

给出一个长度为 $n(\le 2\times 10^6)$ 的数列，有 $m(\le 2\times 10^6)$ 次询问，求 $[l,r]$ 之间有多少个出现了两次及以上的数。

题解

和 HH的项链 差不多，只是要求出现两次。所以把树状数组维护的值修改一下，变成只有出现了两次才更新节点的权值。

先预处理出每种数字下一次和下下次出现的位置 $nxt[]$ 和 $nxt2[]$，并把所有数字出现了两次的位置权值 $+1$ 。

从左至右依次处理每个位置 $j$ ，将 $nxt[j]$ 的权值 $-1$ （去掉 $j$ 后只剩一个了），将 $nxt2[j]$ 的权值 $+1$ 。将询问离线下来按 $l$ 排序，遇到询问就输出。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=2000005;
struct node {
    int l,r,id;
} q[N];
int n,m,k,t[N],nxt[N],nxt2[N],col[N],lst[N],cnt[N],ans[N];

inline void add(int x,int y) { for (;x<=n;x+=x&-x) t[x]+=y; }

inline int query(int x)
{
    int ans=0;
    for (;x;x-=x&-x) ans+=t[x];
    return ans;
}

inline bool cmp(node x,node y) { return x.l<y.l; }

signed main()
{
    n=read(); m=read(); k=read();
    for (int i=1;i<=n;i++) col[i]=read();
    for (int i=1;i<=k;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
    for (int i=n;i;i--)
    {
        nxt2[i]=nxt[nxt[i]=lst[col[i]]];
        lst[col[i]]=i;
    }
    for (int i=1;i<=n;i++) if (++cnt[col[i]]==2) add(i,1);
    sort(q+1,q+k+1,cmp);
    for (int i=1,j=1;i<=k;i++)
    {
        for (;j<q[i].l;j++)
        {
            if (nxt[j]) add(nxt[j],-1);
            if (nxt2[j]) add(nxt2[j],1);
        }
        ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
    }
    for (int i=1;i<=k;i++) printf("%d\n",ans[i]);
    return 0;
}