HDU 3874

和上题HDU 3333一样。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define LL __int64
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N=60050;
const int M=300050;
struct Query{
	int l,r,Id;
	bool operator <(const Query &a)const{
		if(r<a.r) return true;
		return false;
	}
};
LL su[N],ans[M];
int num[N];
Query query[M];
int n,last[N];

LL sum(int x){
  if(x==0) return 0;
  LL s=0;
  for(;x;x-=lowbit(x))s+=su[x];
  return s;
}

void update(int x,int w){
  for(;x<=n;x+=lowbit(x))su[x]+=(LL)w;
}

int main(){
	int T,cnt=0,q;
	scanf("%d",&T);
	while(T--){
		cnt=0;
		scanf("%d",&n);
		map<int,int>mp;
		for(int i=1;i<=n;i++){
			last[i]=0;su[i]=0;
			scanf("%d",&num[i]);
			if(!mp[num[i]]){
				mp[num[i]]=++cnt;
			}
		}
		scanf("%d",&q);
		for(int i=1;i<=q;i++){
			ans[i]=0;
			scanf("%d%d",&query[i].l,&query[i].r);
			query[i].Id=i;
		}
		sort(query+1,query+1+q);
		cnt=1;
		for(int i=1;i<=n&&cnt<=q;i++){
			int t=mp[num[i]];
			if(!last[t]){
				update(i,num[i]);
			}
			else{
				update(last[t],-num[i]);
				update(i,num[i]);
			}
			last[t]=i;
			while(cnt<=q&&query[cnt].r==i){
				ans[query[cnt].Id]=sum(query[cnt].r)-sum(query[cnt].l-1);
				cnt++;
			}
		}
		for(int i=1;i<=q;i++)
		printf("%I64d
",ans[i]);
		
	}
	return 0;
}