洛谷P4113 [HEOI2012]采花题解

题目链接：P4113 [HEOI2012]采花

题意：萧薰儿是古国的公主，平时的一大爱好是采花。

今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。

花园足够大，容纳了 \(n\) 朵花，共有 \(c\) 种颜色，用整数 \(1 \sim c\) 表示。且花是排成一排的，以便于公主采花。公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴。同时，她有一癖好，她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告诉她，她必能再次采到此颜色的花。

由于时间关系，公主只能走过花园连续的一段进行采花，便让女仆福涵洁安排行程。福涵洁综合各种因素拟定了 \(m\) 个行程，然后一一向你询问公主能采到的花共有几种不同的颜色。

\(1 \leq n, c, m \leq 2 \times 10^6\)。

对于全部的测试点，保证 \(1 \leq x_i \leq c\)，\(1 \leq l \leq r \leq n\)。

其实就是 P1972 [SDOI2009] HH的项链改了一改，

本题具体的做法是预处理出所有第二次出现的数的贡献，然后离线处理询问。

~~（作者语文比较烂，不知道这句话放哪里比较好，就放前面来了）~~

下面是详细的解释。

设数组 \(\text{val} = \{1,2,2,3,1,1,3\}\)

要询问一个区间 \([1,7]=\{1,2,2,3,1,1,3\}\)

每个数的贡献是这样的 \(\{0,0,1,0,1,0,1\}\)

实际上我们只需要处理第二次出现的数的贡献即可

因为出现两次是容易处理的，并且小于的不会产生贡献，大于的不会增加贡献

不难发现区间询问可以用树状数组维护贡献

一个暴力的想法是，对于每个询问 \([l,r]\) ，我们扫一遍 \([1,l-1]\)

为什么要扫一遍呢？因为对于出现大于两次的，

我们只把贡献记在了它第二次出现的位置上，

而这个数可能在 \([1,l-1]\) 和 \([l,r]\) 都出现了两次及以上

当然这样暴力扫肯定是不行的，考虑离线处理询问。

把询问按照 \(l\) 从小到大排序，这样我们只要在询问的过程中扫就可以了

时间复杂度 \(O(m \log n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(2e6+15)

struct node
{
    int l,r,id;
}q[N];
int n,k,m,b[N],val[N],nx[N],first[N],ans[N];
struct BIT
{
    int tree[N];
    int lowbit(int x){return x&(-x);}
    void add(int x,int v)
    {
        for(; x<=n; x+=lowbit(x))
            tree[x]+=v;
    }
    int qSum(int x)
    {
        int res=0;
        for(; x>=1; x-=lowbit(x))
            res+=tree[x];
        return res;
    }
}tr;
signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n);read(k);read(m);
    for(int i=1; i<=n; i++) 
        read(val[i]);
    for(int i=n; i>=1; i--)
    {
        nx[i]=first[val[i]];
        first[val[i]]=i;
    }
    for(int i=1; i<=n; i++)
        if(++b[val[i]]==2)tr.add(i,1);
    for(int i=1; i<=m; i++)
    {
        read(q[i].l);read(q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+1+m,[](node a,node b){return a.l<b.l;});
    int now=1;
    for(int i=1; i<=m; i++)
    {
        for(; now<q[i].l; ++now)
        {
            if(nx[now])tr.add(nx[now],-1);
            if(nx[nx[now]])tr.add(nx[nx[now]],1);
        }
        ans[q[i].id]=tr.qSum(q[i].r)-tr.qSum(q[i].l);
    }
    for(int i=1; i<=m; i++)
        write(ans[i]),pc('\n');
    return 0;
}