首页 > ACM题库 > HDU-杭电 > HDU 3333-Turing Tree-线段树-[解题报告]HOJ
2014
03-16

HDU 3333-Turing Tree-线段树-[解题报告]HOJ

Turing Tree

问题描述 :

After inventing Turing Tree, 3xian always felt boring when solving problems about intervals, because Turing Tree could easily have the solution. As well, wily 3xian made lots of new problems about intervals. So, today, this sick thing happens again…

Now given a sequence of N numbers A1, A2, …, AN and a number of Queries(i, j) (1≤i≤j≤N). For each Query(i, j), you are to caculate the sum of distinct values in the subsequence Ai, Ai+1, …, Aj.

输入:

The first line is an integer T (1 ≤ T ≤ 10), indecating the number of testcases below.
For each case, the input format will be like this:
* Line 1: N (1 ≤ N ≤ 30,000).
* Line 2: N integers A1, A2, …, AN (0 ≤ Ai ≤ 1,000,000,000).
* Line 3: Q (1 ≤ Q ≤ 100,000), the number of Queries.
* Next Q lines: each line contains 2 integers i, j representing a Query (1 ≤ i ≤ j ≤ N).

输出:

The first line is an integer T (1 ≤ T ≤ 10), indecating the number of testcases below.
For each case, the input format will be like this:
* Line 1: N (1 ≤ N ≤ 30,000).
* Line 2: N integers A1, A2, …, AN (0 ≤ Ai ≤ 1,000,000,000).
* Line 3: Q (1 ≤ Q ≤ 100,000), the number of Queries.
* Next Q lines: each line contains 2 integers i, j representing a Query (1 ≤ i ≤ j ≤ N).

样例输入:

2
3
1 1 4
2
1 2
2 3
5
1 1 2 1 3
3
1 5
2 4
3 5

样例输出:

1
5
6
3
6

离线查是比较简单的,按查询的右界排序,不断加入a数组并用hash记录位置,如果某个值在前面已经出现过,删除前面那个值,这样下个查询查到这个值的时候,值就不会重复。 写的时候出现3个错误,主要还是对线段树的实现不熟吧,经常用模板的人就是这样…还有类型LL经常忘记写成int。

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

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N=30005;
const int Q=100005;
typedef long long LL;
int n,tt,qq;
map<LL,int> hashs;
LL sum[N*4],a[N],ans[Q];
struct QN{
	int l,r,index;
}q[Q];
int cmp(QN a,QN b){
	return a.r<b.r;
}
void build(int l,int r,int rt){
	sum[rt]=0;
	if(l==r) return;
	int m=(l+r)/2;
	build(lson);
	build(rson);
}

void push_up(int rt){
	sum[rt]=sum[rt*2]+sum[rt*2+1];
}

void update(int a,LL c,int l,int r,int rt){//单点更新a的值为c
	if(l==r){
		sum[rt]=c;//sum[l] --wa1
		return;
	}
	int m=(l+r)/2;
	if(a<=m)
		update(a,c,lson);
	else
		update(a,c,rson);
	push_up(rt);
}

LL query(int a,int b,int l,int r,int rt){
	if(a<=l&&b>=r)
		return sum[rt];
	int m=(l+r)/2;
	LL rst=0;//int -- wa3
	if(a<=m)
		rst+=query(a,b,lson);
	if(b>m)
		rst+=query(a,b,rson);
	return rst;
}

void solve(){
	int pos=1;
	for(int i=0;i<qq;i++){
		while(q[i].r>=pos){//加入a
			if(hashs[a[pos]])//已经出现过
				update(hashs[a[pos]],0,1,n,1);
			hashs[a[pos]]=pos;
			update(pos,a[pos++],1,n,1);//pos++ 建议放下面
		}
		ans[q[i].index]=query(q[i].l,q[i].r,1,n,1);
	}
}

int main(){
	for(cin>>tt;tt>0;tt--){
		hashs.clear();
		cin>>n;
		build(1,n,1);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		cin>>qq;
		for(int i=0;i<qq;i++){//按r排序,离线查
			scanf("%d %d",&q[i].l,&q[i].r);
			q[i].index=i;
		}
		sort(q,q+qq,cmp);
		solve();
		for(int i=0;i<qq;i++)
			printf("%I64d\n",ans[i]);
	}
	return 0;
}

参考:http://blog.csdn.net/mid_kkks/article/details/19681753


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c