D-query SPOJ 树状数组+离线/莫队算法

题意

有一串正数，求一定区间中有多少个不同的数

解题思路——树状数组

说明一下，树状数组开始全部是零。

首先，我们存下所有需要查询的区间，然后根据右端点进行从小到大的排序。然后依次处理这个区间中的答案，仔细想一下，后面的区间答案不会受到影响。

怎么处理区间中的答案呢？

我们按照数字出现的顺序，向树状数组中加一，如果这个数字之前出现了，那么需要树状数组在这个数字上次出现的位置减一，这样可以保证在一定区间内，每个数字都有在树状数组中唯一对应的1，当处理到数字的位置到达某个询问的右端点时，就可以求一下这个询问区间有几个1，这个就是这个区间内不同数字的个数。

这里需要标记数字是否之前出现过，因此就开了一个vis数组，但是题目数字出现的范围太大而输入的数字个数不是很多，因此可以进行离散化，重新进行映射到小的区间中。当然也可以使用map。

点操作+区间求和正好就可以使用树状数组。

下面是代码实现，有注释可以更加清晰。

莫队算法

莫队算法看了好多博客文章，这个题是入门题，思想很巧妙，复杂度在\(O(n*lgn)\)

详解这里就不写了，主要是最近时间比较紧，得赶紧看其他题，这里就推荐一个博客，写的很好，就是背景太花哨了，影响到我阅读。传送门

代码实现（树状数组+莫队算法）

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

typedef long long ll;

const int maxn=3e4+7;

const int maxq=2e5+7;

struct query{

	int L, R, id;

	bool friend operator <(query a, query b)

	{

		return a.R < b.R;

	}

}q[maxq];

int num[maxn]; //存储那一串数字

int bak[maxn]; //备份数字，用来进行离散化

int sum[maxn]; //树状数组

int pre[maxn]; //记录数字之前出现的位置

int vis[maxn]; //标记数字是否出现过

int ans[maxq]; //离线处理，需要记录答案，之后一并输出

int n, m, cnt; //n数字的个数，m个询问，cnt是映射后的范围

void up(int id, int x)

{

	while(id<=n)

	{

		sum[id]+=x;

		id += id&(-id);

	}

} 

ll getsum(int id)

{

	ll ret=0;

	while(id>0)

	{

		ret+=sum[id];

		id -= id&(-id);

	}

	return ret;

}

int getid(int num) //求映射后的编码

{

	return lower_bound(bak, bak+cnt, num)-bak+1;

}

int main()

{

	while(scanf("%d", &n)!=EOF)

	{

		for(int i=1;i<=n; i++) //初始化

		{

			sum[i]=0;

			vis[i]=0;

		}

		for(int i=1; i<=n; i++) //读入数据+备份。

		{

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

			bak[i-1]=num[i];//从0开始便于后面初始化

		}

		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);//排序

		sort(bak, bak+n);//离散化先排序

		cnt=unique(bak, bak+n)-bak;//去重后的个数

		int j=1;

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

		{

			while(j <= q[i].R && j<=n)

			{

				int tmp=getid(num[j]); //获取编号

				if(vis[tmp]!=0)

				{

					up(pre[tmp], -1);

					pre[tmp]=j;

					up(j, 1);

					j++;

				}

				else {

					pre[tmp]=j;

					vis[tmp]=1;

					up(j, 1);

					j++;

				}

			}

			ans[q[i].id]=getsum(q[i].R)-getsum(q[i].L-1);

		}

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

		{

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

		}

	}

	return 0;

}

//莫队算法

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int maxn=3e4+7;

const int maxq=2e5+7;

int a[maxn];

int book[1000007]; //记录是否出现和出现的次数

int ans[maxq];

int block, tmp;

struct node{

	int s, t;

	int id, blk;

	bool friend operator < (node a, node b)

	{

		if(a.blk==b.blk)

			return a.t < b.t;

		return a.s<b.s;

	}

}q[maxq];

void add(int x)

{

	if(book[a[x]]==0)

		tmp++;

	book[a[x]]++;

}

void del(int x)

{

	book[a[x]]--;

	if(book[a[x]]==0)

		tmp--;

}

int main()

{

	int n, m;

	while(scanf("%d", &n)!=EOF)

	{

		memset(book, 0, sizeof(book));

		block=sqrt(n*1.0);

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

		{

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

		}

		scanf("%d", &m);

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

		{

			scanf("%d%d", &q[i].s, &q[i].t);

			q[i].id=i;

			q[i].blk=q[i].s/block;

		}

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

		int l=1, r=0, s, t;

		tmp=0;

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

		{

			s=q[i].s;

			t=q[i].t;

			while(l<s)

			{

				del(l);

				l++;

			}

			while(l>s)

			{

				l--;

				add(l);

			}

			while(r<t)

			{

				r++;

				add(r);

			}

			while(r>t)

			{

				del(r);

				r--;

			}

			ans[q[i].id]=tmp;

		}

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

		{

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

		}

	}

	return 0;

}

巴特西

D-query SPOJ 树状数组+离线

D-query SPOJ 树状数组+离线/莫队算法

题意

解题思路——树状数组

莫队算法

代码实现（树状数组+莫队算法）

最新文章

热门文章