hdu 3874（树状数组+离线算法）

解题思路：这道题和之前的题一样，查找[l,r]区间内不重复数字的和。可以利用离线算法，实际上离线算法为了解决在查找时出现的矛盾，因为每次询问的区间大小不同，如果单独处理的话可能会对之后的查询有影响，所以离线算法帮助我们把要查询的区间先按照右端点进行排序，因为在处理更靠右的区间时，比它小的区间肯定是已经得到的不重复的数了，所以不会影响到后面的查找。

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

const int M = 200005;
const int N = 50005;
struct Query
{
	int l,r,id;
	
	bool operator < (Query a)
	{
		return r < a.r;
	}
}q[M];
int n,m,size;
int tree[N<<1],arr[N],tmp[N],last[N],ans[M];

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

void update(int x,int d)
{
	for(int i = x; i <= n; i += lowbit(i))
		tree[i] += d;
}

int getsum(int x)
{
	int sum = 0;
	for(int i = x; i > 0; i -= lowbit(i))
		sum += tree[i];
	return sum;
}

int bisearch(int val)
{
	int l = 1, r = size, mid;
	while(l <= r)
	{
		mid = (l + r) >> 1;
		if(tmp[mid] == val) return mid;
		else if(tmp[mid] > val)
			r = mid - 1;
		else l = mid + 1;
	}
}

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		cin >> n;
		for(int i = 1; i <= n; i++)
		{
			cin >> arr[i];
			tmp[i] = arr[i];
		}
		cin >> m;
		for(int i = 1; i <= m; i++)
		{
			cin >> q[i].l >> q[i].r;
			q[i].id = i;
		}
		sort(tmp+1,tmp+1+n);
		sort(q+1,q+1+m);
		//离散化
		size = 1;
		for(int i = 2; i <= n; i++)
			if(tmp[i] != tmp[i-1])
				tmp[++size] = tmp[i];
		memset(tree,0,sizeof(tree));
		memset(last,0,sizeof(last));
		int idx = 1;
		for(int i = 1; i <= n; i++)
		{
			int x = bisearch(arr[i]);
			if(last[x])
				update(last[x],-arr[i]);
			update(i,arr[i]);
			last[x] = i;
			while(q[idx].r == i && idx <= m)
			{
				ans[q[idx].id] = getsum(q[idx].r) - getsum(q[idx].l - 1);
				idx++;
			}
		}
		for(int i = 1; i <= m; i++)
			cout << ans[i] << endl;
	}
	return 0;
}

最后

以上就是彪壮春天为你收集整理的hdu 3874（树状数组+离线算法）的全部内容，希望文章能够帮你解决hdu 3874（树状数组+离线算法）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。