HDU - 3333 Turing Tree(线段树+离线处理)

题目链接：点击查看

题目大意：给定一个长度为n的数列，依次求m个区间中不相同数字之和

题目分析：n给的是3e4，看到区间问题先要想到线段树或差分区间或动态规划，暴力是肯定不行滴，那么这个题已经知道是需要

用线段树处理了，可是我们只擅长用线段树求区间和，并没有学过求不同数字之和啊，那么该怎么处理重复的数字呢？

这里就要将线段树的两个优势结合起来使用了：单点修改和区间查询

好了，现在来说一下这个题的大体思路，然后在说一下具体实现方法吧：

首先，对于所有的区间查询，我们先采用离线处理的方法，即先将每一个区间都保存起来，记录一下左右端点以及每一个查询的

编号，然后对其右端点进行升序排序，这样可以保证接下来操作的可行性。

接下来我们要依次遍历每个区间，在这个区间内加点，即将点加入线段树中，加点也是有技巧的，我们必须保证相同的数值，只

有在区间中最右边的那个存在，其余位置的这个数字都不能存在，（因为习惯原因，遍历都是从1到n遍历，即从左到右遍历，所

以最右边就是目前最后一个出现的）。综上所述，令加点和查询依次交替进行，并用一个数组存起来，最后依次输出即可。

然后我来讲一下怎么具体实现这些细节：

对于排序，没什么好说的，这个题虽然每个位置的数字范围很大，但是不需要离散化，因为利用下标计算足矣。

然后是如何实现上述加点的过程呢？我们需要一个hash数组来记录每个点最后在线段树中出现的位置，若准备加入的点在以前已

经加入过了，我们只需要将上一个位置的这个点先删除掉，即上一次位置的数字设置为0，然后再加入本次位置的这个点就好

了，然后这个加点的操作可以一直从第一个点维护到区间的右端点，因为维护的过程中保证了线段树中：

1. 不会出现两个相同数值的点
2. 从左至右依次进行加点操作
3. 及时删除掉将会重复的点

这样就可以维护题目中给出的条件了，上代码：

PS：这个题一开始做的时候真的想抽自己，最后输出的ans数组一开始手残写成a数组了，输出的时候怎么输出怎么不对，调试的时候怎么调试怎么没问题，真的服了，看来我真的太弱了

#include<iostream>
#include<cstdio> 
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<cmath>
using namespace std;

typedef long long LL;

const int inf=0x3f3f3f3f;

const int N=1e5+100;

int a[N];

LL ans[N];

struct Node
{
	int l,r;
	LL sum;
}tree[N<<1];

struct node
{
	int x,y,id;
}p[N];

map<int,int>vis;

void build(int k,int l,int r)
{
	tree[k].l=l;
	tree[k].r=r;
	tree[k].sum=0;
	if(l==r)
		return;
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}

void update(int k,int pos,int val)
{
	if(tree[k].l==tree[k].r)
	{
		tree[k].sum=val;
		return;
	}
	int mid=(tree[k].l+tree[k].r)>>1;
	if(mid>=pos)
		update(k<<1,pos,val);
	else
		update(k<<1|1,pos,val);
	tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}

LL query(int k,int l,int r)
{
	if(tree[k].r<l||tree[k].l>r)
		return 0;
	if(tree[k].l>=l&&tree[k].r<=r)
		return tree[k].sum;
	return query(k<<1,l,r)+query(k<<1|1,l,r);
}

bool cmp(node a,node b)
{
	return a.y<b.y;
}

int main()
{
//	freopen("input.txt","r",stdin);
	int w;
	cin>>w;
	while(w--)
	{
		int n;
		scanf("%d",&n);
		build(1,1,n);
		vis.clear();
		for(int i=1;i<=n;i++)
			scanf("%d",a+i);
		int m;
		scanf("%d",&m);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&p[i].x,&p[i].y);
			p[i].id=i;
		}
		sort(p+1,p+1+m,cmp);
		int pos=1;
		for(int i=1;i<=m;i++)
		{
			while(pos<=p[i].y)
			{
				if(vis[a[pos]])
					update(1,vis[a[pos]],0);
				vis[a[pos]]=pos;
				update(1,pos,a[pos]);
				pos++;
			}
//			cout<<query(1,p[i].x,p[i].y)<<endl;
			ans[p[i].id]=query(1,p[i].x,p[i].y);
//			cout<<p[i].id<<endl;
		}
		for(int i=1;i<=m;i++)
			cout<<ans[i]<<endl;
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	return 0;
}