[bzoj1878][SDOI2009]HH的项链

HH的项链 bzoj-1878 SDOI-2009

题目大意：给定一个n个数的序列，m次查询。查询区间数的种类个数。

注释：$1\le n \le 5\cdot 10^4$，$1\le m\le 2\cdot 10^5$。

想法：在线的我不会啊qwq。

我们考虑离线做法，将所有的询问以左端点递增为关键字排序。

nxt数组表示当前位置的数的后面第一个和它相等的位置。

这样我们从1枚举到n，将当前的val[i]--，val[nxt[i]]++。然后查询前缀和相减就可以了。

开始的时候第一个出现的种类为1，其余都是0。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 50010

#define M 200010

using namespace std;

struct Node

{

	int l,r,id,ans;

}q[M];

int nxt[N<<1],tree[N],a[N],p[1000005],n;

inline bool cmp1(const Node &x,const Node &y)

{

	return x.l==y.l?x.r<y.r:x.l<y.l;

}

inline bool cmp2(const Node &x,const Node &y)

{

	return x.id<y.id;

}

inline int lowbit(int x) {return x&(-x);}

void update(int x,int val)

{

	for(int i=x;i<=n+1;i+=lowbit(i))

	{

		tree[i]+=val;

	}

}

int query(int x)

{

	int ans=0;

	for(int i=x;i>=1;i-=lowbit(i))

	{

		ans+=tree[i];

	}

	return ans;

}

int main()

{

	cin >> n ;

	int mx=0;

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&a[i]);

		mx=max(mx,a[i]);

	}

	for(int i=n;i>=1;i--)

	{

		nxt[i]=p[a[i]];

		p[a[i]]=i;

	}

	for(int i=1;i<=mx;i++)

	{

		if(p[i]) update(p[i],1);

	}

	int m; scanf("%d",&m);

	for(int i=1;i<=m;i++)

	{

		scanf("%d%d",&q[i].l,&q[i].r);

		q[i].id=i;

	}

	sort(q+1,q+m+1,cmp1);

	int l=1;

	for(int i=1;i<=m;i++)

	{

		while(l<q[i].l)

		{

			if(nxt[l]) update(nxt[l],1);

			update(l,-1);

			l++;

		}

		q[i].ans=query(q[i].r)-query(q[i].l-1);

	}

	sort(q+1,q+m+1,cmp2);

	for(int i=1;i<=m;i++)

	{

		printf("%d\n",q[i].ans);

	}

	return 0;

}

小结：离线好强大啊...

巴特西

[bzoj1878][SDOI2009]HH的项链_树状数组

最新文章

热门文章