Turing Tree HDU - 3333 T7 D24
查找区间不同元素和。
思路：
离线做法，将所有询问按r值升序排序。线段树维护区间和，遍历整个数组，到某个元素时，若这个元素之前出现过，将之前出现过的位置值变为0，当前位置值设为元素值。查询时区间查询即可
/*
#########
############
#############
## ###########
### ###### #####
### ####### ####
### ########## ####
#### ########### ####
##### ########### #####
###### ### ######## #####
##### ### ######## ######
###### ### ########### ######
###### #### ############## ######
####### ##################### #######
####### ##############################
####### ###### ################# #######
####### ###### ###### ######### ######
####### ## ###### ###### ######
####### ###### ##### #####
###### ##### ##### ####
##### #### ##### ###
##### ;### ### #
## #### ####
*/
#include<iostream>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<string.h>
#define ll long long
#define ls (p<<1)
#define rs ((p<<1)|1)
#define mid ((t[p].l+t[p].r)>>1)
using namespace std;
int read(){int x=0,f=1;char ch=getchar();while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(int x){if(x < 0){putchar(‘-‘);x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + ‘0‘);}
const int qs=2e5+7;
struct Tree{
ll l,r,cnt,val;
#define l(x) t[x].l
#define r(x) t[x].r
#define val(x) t[x].val
}t[qs<<2];
ll T,n,q,A[qs],C[qs],pre[qs];
struct node{
int l,r,id;
}B[qs];
void build(int p,int l,int r){
l(p)=l,r(p)=r;
val(p)=0;
if(l==r) {
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
}
void update(int p,int l,int r,int k){
if(l<=l(p)&&r>=r(p)){
val(p)=k;
return ;
}
if(l<=mid) update(ls,l,r,k);
if(r>mid) update(rs,l,r,k);
val(p)=val(ls)+val(rs);
}
ll ask(int p,int l,int r){
if(l<=l(p)&&r>=r(p)) return val(p);
ll val=0;
if(l<=mid) val+=ask(ls,l,r);
if(r>mid) val+=ask(rs,l,r);
return val;
}
bool cmp(node a,node b){
if(a.r==b.r) return a.l<b.l;
return a.r<b.r;
}
ll ans[qs];
map<int,int> mp;
int main(){
T=read();
while(T--){
mp.clear();
n=read();
for(int i=1;i<=n;++i) {
A[i]=read();
pre[i]=mp[A[i]];
mp[A[i]]=i;
}
q=read();
for(int i=1;i<=q;++i){
B[i].l=read();
B[i].r=read();
B[i].id=i;
}
sort(B+1,B+1+q,cmp);
build(1,1,n);
int l=1,r=1;
for(int i=1;i<=q;++i){
for(;r<=B[i].r;++r) {
if(pre[r]) update(1,pre[r],pre[r],0);
update(1,r,r,A[r]);
}
ans[B[i].id]=ask(1,1,B[i].r)-ask(1,1,B[i].l-1);
}
for(int i=1;i<=q;++i){
cout<<ans[i]<<"\n";
}
}
return 0;
}