http://acm.hdu.edu.cn/showproblem.php?pid=3333
Turing Tree
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2614 Accepted Submission(s): 892
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.
3
1 1 4
2
1 2
2 3
5
1 1 2 1 3
3
1 5
2 4
3 5
5
6
3
6
很不错的一道线段树题目，做了两天，终于给弄明白了。。。
看别人blog的时候，发现总是说离散化，，不明白什么意思。。。上网搜了下，其实就是一种思想的转化，，有时候我们一直在用，只不过不知道叫什么名字罢了。。。
比如对于这道题， 我们如果讨论一个数，判断它前面是否出现过，，因为0 ≤ Ai ≤ 1,000,000,000 ，很显然我们不能直接 用一个visit去判断。。
但是由于1 ≤ N ≤ 30,000 ，我们可以开一个30000的数组，然后把这些数存起来，排好序， 之后再判断一个数是否出现过的时候， 就可以用二分找到它的下标。。
对下表进行visit记录就可以了。。。
题意： 给出一个长度为N(N <= 30000)的数列，然后是一连串询问，询问数<= 100000，问给定区间内不同数字的和。
因为数字的范围较大，所以首先是对数列进行离散化，一般可以用二分或者hash，将大范围的数字映射到连续的区间。
然后一次性读入所有的区间（整数对），并且对整数对的右端点进行递增排序。这里注意，要记录下整数对读入的位置下标。。。
接下来按顺序枚举每个数字a[i]，如果a[i]之前出现过，就将a[i]之前位置的值删除，然后在当前位置插入，当枚举的位置和区间对中某个位置相 等时执行询问操作。。。。
题解部分转自：http://www.cnblogs.com/183zyz/archive/2011/04/22/2025060.html
【code】：
/**
judge status: Accepted exe.time:640ms
exe.memory 3696k language:C++
*/ #include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm> #define N 100010
#define M 30010 #define lson p<<1
#define rson p<<1|1 using namespace std; struct FTI{
int from,to,idx; //查询的始末位置 以及 索引位置
}fti[N]; struct Nod{
int l,r;
__int64 sum;
}node[M<<]; int temp[M],index[M],a[M],visit[M],k; __int64 ans[N]; bool cmp(FTI a,FTI b) //结构体排序调用函数
{
return a.to<b.to;
} void building(int l,int r,int p)
{
node[p].sum=;
node[p].l=l;
node[p].r=r;
if(l==r) return;
int mid=(l+r)/;
building(l,mid,lson);
building(mid+,r,rson);
} int findPos(int val) //二分查找值val在index中的位置
{
int l,r,mid;
l=;
r=k;
while(l<=r)
{
mid=(l+r)/;
if(index[mid]>val) r=mid-;
else if(index[mid]<val) l=mid+;
else return mid;
}
return -;
} void update(int id,int p,int val) //更新
{
if(node[p].l==node[p].r)
{
node[p].sum+=val;
return;
}
int mid = (node[p].l+node[p].r)>>;
if(id<=mid) update(id,lson,val);
else update(id,rson,val);
node[p].sum = node[lson].sum + node[rson].sum;
} __int64 Query(int l,int r,int p)
{
if(node[p].l==l&&node[p].r==r)
{
return node[p].sum;
}
int mid = (node[p].l+node[p].r)>>;
if(r<=mid) return Query(l,r,lson);
else if(l>mid) return Query(l,r,rson);
else return Query(l,mid,lson)+Query(mid+,r,rson);
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,i,j;
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%d",a+i+);
temp[i]=a[i+];
}
sort(temp,temp+n);//排序
index[]=temp[];
j=;
for(i=;i<n;i++)
{
if(index[j]!=temp[i])
{
index[++j]=temp[i]; //消除重复数字
}
}
k=j;
memset(visit,,sizeof(visit));
int m;
scanf("%d",&m);
for(i=;i<=m;i++)
{
scanf("%d%d",&fti[i].from,&fti[i].to);
fti[i].idx = i;
}
sort(fti+,fti+m+,cmp); //结构体按to排序
building(,n,);
j=;
int id,pos;
for(i=;i<=n;i++)
{
id = findPos(a[i]);
pos = visit[id];
if(pos) update(pos,,-a[i]); //如果前面出现过a[i]，则减掉前面的a[i]
update(i,,a[i]); //在i的位置增加a[i]
visit[id] = i; //标记出现过
while(j<=m&&i==fti[j].to)
{
ans[fti[j].idx] = Query(fti[j].from,fti[j].to,); //如果到了to的位置，就是需要统计的时候了，结果放到ans里面
j++;
}
}
for(i=;i<=m;i++)
{
printf("%I64d\n",ans[i]);
}
}
return ;
}