HDU 3333 Turing Tree (线段树)
Turing Tree
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4768 Accepted Submission(s): 1686
Problem Description
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.
Input
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).
Output
For each Query, print the sum of distinct values of the specified subsequence in one line.
Sample Input
2
3
1 1 4
2
1 2
2 3
5
1 1 2 1 3
3
1 5
2 4
3 5Sample Output
1
5
6
3
6
询问任意区间里有多少个不相同的数字，首先要想到，判断某个数字是否出现区间里，肯定是看的它的位置是否在区间内，那么重复的数字怎么办呢，我们只要记录这个数字最后一个位置就好了，因为这个数字是否出现在区间里，通过它最后一个出现的位置，完全可以决定。遇到这种10万个询问区间的问题，如果题目不是强制要求在线，我们应该考虑离线做，这样会简单很多把区间按照右端点排序，也可以按照左端点，然后逐个将数字插入线段树中，遇到右端点就开始查询查询这个区间的和，点更新的时候，如果之前出现过，先删除，再更新位置。这些操作，都可以用线段树解决
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
typedef long long int LL;
const int maxn=3*1e4;
LL num[maxn*4+5];
LL a[maxn+5];
LL aa[maxn+5];
int cot;
LL c[maxn+5];
map<LL,int> m;
int st[maxn+5];
struct Node
{
int l,r;
int tag;
LL ans;
}b[100005];
int n;
void pushup(int node)
{
num[node]=num[node<<1]+num[node<<1|1];
}
void update(int node,int l,int r,int val,LL tag)
{
if(l==r)
{
num[node]=tag;
return;
}
int mid=(l+r)>>1;
if(val<=mid) update(node<<1,l,mid,val,tag);
else update(node<<1|1,mid+1,r,val,tag);
pushup(node);
}
LL query(int node,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
return num[node];
int mid=(l+r)>>1;
LL ret=0;
if(L<=mid) ret+=query(node<<1,l,mid,L,R);
if(R>mid) ret+=query(node<<1|1,mid+1,r,L,R);
return ret;
}
int cmp(Node a,Node b)
{
if(a.r==b.r)
return a.l<b.l;
return a.r<b.r;
}
int cmp2(Node a,Node b)
{
return a.tag<b.tag;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(num,0,sizeof(num));
m.clear();
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
c[i]=a[i];
}
sort(a+1,a+n+1);
int pos=0;
for(int i=1;i<=n;i++)
if(!m[a[i]]) m[a[i]]=++pos;
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&b[i].l,&b[i].r);
b[i].tag=i;
}
sort(b+1,b+1+q,cmp);
int k=1;
memset(st,0,sizeof(st));
for(int i=1;i<=n;i++)
{
if(st[m[c[i]]])
update(1,1,n,st[m[c[i]]],0);
st[m[c[i]]]=i;
update(1,1,n,i,c[i]);
while(i==b[k].r&&k<=q)
{
b[k].ans=query(1,1,n,b[k].l,b[k].r);
k++;
}
}
sort(b+1,b+q+1,cmp2);
for(int i=1;i<=q;i++)
printf("%lld\n",b[i].ans);
}
return 0;
}