题意：
询问一个区间中的不同数的和，例如 1 1 1 2 3 这个区间的和为6
分析：
离线处理，按照右区间端点值进行排序，然后记录之前这个点是否出现过进行更改。然后最后查询区间和。
处理完后就是很普通的线段树单点操作区间求和。
#include<bits/stdc++.h> using namespace std; const int maxn=3e4; typedef long long ll; int a[maxn]; struct node{ int l,r,id; }q[100005]; ll ans[100005]; ll tree[maxn<<2]; bool cmp(node x,node y){ return x.r<y.r; } void update(int l,int r,int i,int x,int y){ if(l==r){ tree[i]+=y; return ; } int mid=l+r>>1; if(x<=mid) update(l,mid,i<<1,x,y); else update(mid+1,r,i<<1|1,x,y); tree[i]=tree[i<<1]+tree[i<<1|1]; } ll query(int l,int r,int i,int x,int y){ if(l>y||r<x) return 0; if(l>=x&&r<=y){ return tree[i]; } int mid=l+r>>1; return query(l,mid,i<<1,x,y)+query(mid+1,r,i<<1|1,x,y); } int main(){ int T; scanf("%d",&T); while(T--){ int n,m; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } scanf("%d",&m); for(int i=0;i<m;i++){ scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i; } sort(q,q+m,cmp); map<int,int> mp; int p=0,x,y; memset(tree,0,sizeof tree); for(int i=0;i<m;i++){ while(p<q[i].r){ p++; if(mp.count(a[p])){ x=mp[a[p]];y=-a[p]; update(1,n,1,x,y); } x=p,y=a[p]; update(1,n,1,x,y); mp[a[p]]=p; } x=q[i].l;y=q[i].r; ans[q[i].id]=query(1,n,1,x,y); } for(int i=0;i<m;i++){ printf("%lld\n",ans[i]); } } return 0; }
