//对询问进行离线操作，读入所有的询问，然后将所有询问按照右升序排序
//在处理第i个询问时，保证从第一个数到第i个询问的右边范围ri的所有和只是前面不相同的点的和
//而且每个点的相同点的位置都是在ri范围内最后一个点，由于在第i次询问后的
//所有询问的右范围都大于ri，所以删除相同的点不会影响后面的询问
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxm = 200010;
__int64 tree[4*maxm] ;
struct node
{
int l,r;
int id ;
}query[maxm] ;
__int64 ans[maxm] ;
int last[5*maxm] ;
int a[maxm] ;
int N,M;
bool cmp(struct node a,struct node b)
{
return a.r < b.r;
}
__int64 getsum(int x)
{
__int64 sum = 0;
while(x)
{
sum += tree[x] ;
x -= (x & -x) ;
}
return sum ;
}
void update(int x , int dx)
{
while(x <= N)
{
tree[x] += dx ;
x += (x & -x);
}
}
void init()
{
memset(last, 0 ,sizeof(last)) ;
memset(tree, 0 ,sizeof(tree)) ;
}
int main()
{
//freopen("in.txt","r",stdin) ;
int T ;
scanf("%d" , &T) ;
while(T--)
{
init() ;
scanf("%d" , &N) ;
for(int i = 1;i <= N;i++)
{
scanf("%d" , &a[i]) ;
if(!last[a[i]])
last[a[i]] = i;
update(i , a[i]) ;
}
scanf("%d" , &M) ;
for(int i = 1;i <= M;i++)
{
scanf("%d%d", &query[i].l ,&query[i].r) ;
query[i].id = i ;
}
sort(query+1,query+1+M ,cmp) ;
int last_right = 1;
for(int i = 1;i <= M;i++)
{
for(int j = last_right;j <= query[i].r ; j++)
if(last[a[j]] != j)
{
update(last[a[j]], -a[j]) ;
last[a[j]] = j;
}
last_right = query[i].r;
ans[query[i].id] = getsum(query[i].r) - getsum(query[i].l-1) ;
}
for(int i = 1;i <= M;i++)
printf("%I64d\n", ans[i]) ;
}
return 0;
}
原文：http://blog.csdn.net/cq_pf/article/details/44754437