P1972 [SDOI2009] HH的项链 题解

· · 题解

P1972 [SDOI2009] HH的项链 题解

补一个扫描线题解。

解法

一句话题意：给定一个序列，多次询问区间 [l,r] 中有多少种不同的数。

我们设序列中 a_i 上一次出现的位置为 pre_i，如果 a_i 没有出现过，则 pre_i = 0。不难发现如果一种数在区间中出现多次，只会产生一次贡献。不妨钦定每种数产生贡献的位置是区间中第一次出现的位置，这时可以发现，产生的总贡献即为 pre_x \le l - 1 的个数，反证法易证。

现在问题即为：给定一个序列 pre，多次查询区间 [l,r] 中有多少个 pre_i \le l - 1。

我们把每一个 pre_i 抽象到二维平面的点上，把 i 看作横坐标，pre_i 看作纵坐标，问题既转化为了经典的二维数点问题，每次询问左下角为 (l,0)，右上角为 (r,l - 1) 的矩形中有几个点。

注意到这个询问是可差分的，我们可以将询问差分为左下角为 (0,0)，右上角为 (r,l - 1) 的矩形减去左下角为 (0,0)，右上角为 (l - 1,l - 1) 的矩形有几个点，这样方便我们使用扫描线思想。

我们将所有操作按横坐标排序（包括加点操作和查询操作），建立权值线段树，维护每个纵坐标出现个数。从左向右扫，如果遇到加点操作就在其纵坐标相应的线段树位置上加 1，如果遇到查询操作就查询线段树中 [0,val] 的个数。

单次操作复杂度 \mathcal{O}(\log n)，共有 n 次加点操作和 2m 次查询操作，总时间复杂度 \mathcal{O}((n + m) \log n)。

代码

#include<bits/stdc++.h>
namespace fast_IO
{
    /**
     * 快读快写
    */
};
using namespace fast_IO;
int n,m,a[1000010],pre[1000010],lst[1000010],ans[1000010],tot;
struct ope
{
    int type,x,y,id;
    inline bool operator<(const ope &rhs) const
    {
        if(x==rhs.x) return type<rhs.type;
        return x<rhs.x;
    }
};
ope op[3000010];
struct node
{
    int cnt;
    node *lc,*rc;
    inline node()
    {
        cnt=0,lc=rc=nullptr;
    }
    inline void pushup()
    {
        cnt=lc->cnt+rc->cnt;
    }
};
class seg_tree
{
    #define ls l,mid
    #define rs mid+1,r
private:
    node *root;
    inline node *build(int l,int r)
    {
        node *rt=new node();
        if(l<r)
        {
            int mid=(l+r)/2;
            rt->lc=build(ls),rt->rc=build(rs);
        }
        return rt;
    }
    inline void fix(node *rt,const int pos,int l,int r)
    {
        if(l==r)
        {
            rt->cnt++;
            return;
        }
        int mid=(l+r)/2;
        if(pos<=mid) fix(rt->lc,pos,ls);
        else fix(rt->rc,pos,rs);
        rt->pushup();
    }
    inline int ask(node *rt,const int L,const int R,int l,int r)
    {
        if(L<=l && r<=R) return rt->cnt;
        int mid=(l+r)/2,ret=0;
        if(L<=mid) ret+=ask(rt->lc,L,R,ls);
        if(R>mid) ret+=ask(rt->rc,L,R,rs);
        return ret;
    }
public:
    inline void build()
    {
        root=build(0,n);
    }
    inline void fix(const int pos)
    {
        fix(root,pos,0,n);
    }
    inline int ask(const int L,const int R)
    {
        return ask(root,L,R,0,n);
    }
};
seg_tree tree;
int main()
{
    in>>n,tree.build();
    for(int i=1;i<=n;i++) in>>a[i],pre[i]=lst[a[i]],lst[a[i]]=i,op[++tot]=(ope){0,i,pre[i],i};
    in>>m;
    for(int i=1,l,r;i<=m;i++) in>>l>>r,op[++tot]=(ope){1,r,l-1,i},op[++tot]=(ope){2,l-1,l-1,i};
    std::sort(op+1,op+tot+1);
    for(int i=1;i<=tot;i++)
    {
        if(op[i].type==0) tree.fix(op[i].y);
        else if(op[i].type==1) ans[op[i].id]+=tree.ask(0,op[i].y);
        else ans[op[i].id]-=tree.ask(0,op[i].y);
    }
    for(int i=1;i<=m;i++) out<<ans[i]<<'\n';
    fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
    return 0;
}