P1972 [SDOI2009] HH的项链 题解

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;
}