【洛谷P1972】HH的项链

佚名 4年前 (2020-01-17) 随笔 1944人围观抢沙发百度已收录

题目

题目链接：https://www.luogu.com.cn/problem/P1972
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。
有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

思路

之前写的是莫队的\(O(n\sqrt{n})\)的算法。现在数据又加强了，于是回来写了一个\(O(n\log n)\)的算法。
考虑对于一堆\(r_i=x\)的询问\(i\)，我们发现，如果一个数字在\([1,x]\)中出现了多次，那么取最大的且不超过\(x\)位置的数字显然是最优的。
那么我们在处理一堆右端点相同的询问时，我们只要知道在\([1,x]\)中每个数字出现位置最后的位置在哪里即可。
建立一棵树状数组，处理到\(x=i\)时，树状数组中位置\(j\)表示在区间\([1,i]\)中，位置\(j\)上的数字是否是最后出现的（所以有\(c[i]\in \{0,1\}\)）。那么此时对于一个询问\([l,x]\)，答案就是\(\sum^{x}_{i=l}c[i]\)。树状数组\(O(\log n)\)搞定。
在从位置\(i\)的询问转移到位置\(i+1\)的询问时，我们将\(a[i+1]\)上一次出现的位置在树状数组中清零，在位置\(i+1\)标记为1。仍然\(O(\log n)\)
时间复杂度\(O(n\log n)\)

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

const int N=1000010;
int n,m,a[N],last[N],ans[N];

struct ASK
{
    int l,r,id;
}ask[N];

struct BIT
{
    int c[N];
    
    int ask(int x)
    {
        int sum=0;
        for (int i=x;i;i-=i&-i)
            sum+=c[i];
        return sum;
    }
    
    void add(int x,int val)
    {
        if (!x) return;
        for (int i=x;i<=n;i+=i&-i)
            c[i]+=val;
    }
}bit;

bool cmp(ASK x,ASK y)
{
    return x.r<y.r;
}

int read()
{
    int d=0,f=1; char ch=getchar();
    while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
    while (isdigit(ch)) d=(d<<3)+(d<<1)+ch-48,ch=getchar();
    return d*f;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    m=read();
    for (int i=1;i<=m;i++)
        ask[i].l=read(),ask[i].r=read(),ask[i].id=i;
    sort(ask+1,ask+1+m,cmp);
    for (int i=1;i<=m;i++)
    {
        for (int j=ask[i-1].r+1;j<=ask[i].r;j++)
            bit.add(last[a[j]],-1),bit.add(j,1),last[a[j]]=j;
        ans[ask[i].id]=bit.ask(ask[i].r)-bit.ask(ask[i].l-1);
    }
    for (int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}