P1972 [SDOI2009] HH的项链 题解
补一个扫描线题解。
解法
一句话题意:给定一个序列,多次询问区间 [ l , r ] [l,r] [l,r] 中有多少种不同的数。
我们设序列中 a i a_i ai 上一次出现的位置为 p r e i pre_i prei,如果 a i a_i ai 没有出现过,则 p r e i = 0 pre_i = 0 prei=0。不难发现如果一种数在区间中出现多次,只会产生一次贡献。不妨钦定每种数产生贡献的位置是区间中第一次出现的位置,这时可以发现,产生的总贡献即为 p r e x ≤ l − 1 pre_x \le l - 1 prex≤l−1 的个数,反证法易证。
现在问题即为:给定一个序列 p r e pre pre,多次查询区间 [ l , r ] [l,r] [l,r] 中有多少个 p r e i ≤ l − 1 pre_i \le l - 1 prei≤l−1。
我们把每一个 p r e i pre_i prei 抽象到二维平面的点上,把 i i i 看作横坐标, p r e i pre_i prei 看作纵坐标,问题既转化为了经典的二维数点问题,每次询问左下角为 ( l , 0 ) (l,0) (l,0),右上角为 ( r , l − 1 ) (r,l - 1) (r,l−1) 的矩形中有几个点。
注意到这个询问是可差分的,我们可以将询问差分为左下角为 ( 0 , 0 ) (0,0) (0,0),右上角为 ( r , l − 1 ) (r,l - 1) (r,l−1) 的矩形减去左下角为 ( 0 , 0 ) (0,0) (0,0),右上角为 ( l − 1 , l − 1 ) (l - 1,l - 1) (l−1,l−1) 的矩形有几个点,这样方便我们使用扫描线思想。
我们将所有操作按横坐标排序(包括加点操作和查询操作),建立线段树,维护每个纵坐标出现个数。从左向右扫,如果遇到加点操作就在其纵坐标相应的线段树位置上加 1 1 1,如果遇到查询操作就查询线段树中 [ 0 , v a l ] [0,val] [0,val] 的个数。
单次操作复杂度 O ( log n ) \mathcal{O}(\log n) O(logn),共有 n n n 次加点操作和 2 m 2m 2m 次查询操作,总时间复杂度 O ( ( n + m ) log n ) \mathcal{O}((n + m) \log n) O((n+m)logn)。
代码
#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;
}