HH的项链---树状数组

题目描述

我csdn博客

点这里

思路

某一段贝壳中，包含了多少种不同的贝壳？

最开始看见这道题时，没有思路

但再看看，可以非常明了的发现这是一个树状数组ban题

设有一长为5的项链

1 2 3 2 1

然后 m = 3

1 5

2 5

1 3

我的思路是这样，由于要求的是种类数 != 求l 到 r 的个数

每种贝壳只能存一个（不能反复存）

也就是说必须删去一些相同的贝壳且删除的不能影响求得答案

比如：上面的1 2 3 2 1，去重，用-1表示删去的

1 2 3 -1 -1

如果像这样，求 l=2,r=5时结果为2

而实际结果为3

所以我们得排个序，按r的升序

遍历i，当i所在位置贝壳前面没有时，update(i,1)

否则update(i,1)且删去前一个

所以又需要一个数组Glod来记录前一个贝壳的地址

便有了如下代码

code

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

const int MAXN = 500001;
const int NUM = 1000001;
int n,Bit[MAXN],Pr[MAXN],Glod[MAXN];
int k[NUM];

inline void Read(int *x)
{
	*x = 0;
	char a = getchar();
	bool f = 0;
	while(a < '0'||a > '9') {if(a == '-') f = 1;a = getchar();}
	while(a >= '0'&&a <= '9') {*x = *x * 10 + a - '0';a = getchar();}
	if(f)
		*x *= -1;
}
class T
{
	int lowbit(int x)
	{
		return x & (-x);
	}
	public:
		bool operator <(const T w) const
		{
			if(r < w.r)
				return 1;
			if(r == w.r)
				if(l < w.l)
					return 1;
			return 0;
		}
		int l,r,num;
		void update(int,int);
		int Sum(int);
}a[MAXN];
void T::update(int Index,int delta)
{
	int i = Index;
	for(;i <= n;i += lowbit(i))
		Bit[i] += delta;
}
int T::Sum(int Index)
{
	int ans = 0,i = Index;
	for(;i > 0;i -= lowbit(i))
		ans += Bit[i];
	return ans;
}
int  main()
{
	int i,m;
	Read(&n);
	for(i = 1;i <= n;i++)
		scanf("%d",&Glod[i]);
	Read(&m);
	for(i = 1;i <= m;i++)
	{
		Read(&a[i].l),Read(&a[i].r);
		a[i].num = i;	
	}
	sort(a + 1,a + 1 + m);
	int q = 1;
	for(i = 1;i <= a[m].r;i++)
	{
		if(!k[Glod[i]])
		{
			k[Glod[i]] = i;
			a[i].update(i,1);
		} else {
			a[i].update(k[Glod[i]],-1);
			k[Glod[i]] = i;
			a[i].update(i,1);
		}
		while(i == a[q].r)
		{
			Pr[a[q].num] = a[q].Sum(a[q].r) - a[q].Sum(a[q].l - 1);
			q++;
		}
	}
	for(i = 1;i < m;i++)
		printf("%d
",Pr[i]);
	printf("%d",Pr[m]);
	return 0;
}