2014
03-16

# 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

#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;
}

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