只查询区间不同的数的和（思路好题）
对查询离线
不断的往每个位置插值 并把前面位置的值置为0 每查到一个右端点 查询一下 （等价操作的转换）
离散化一下
#include<bits/stdc++.h> #define Mem(a,b) memset(a,b,sizeof(a)) #define lson root<<1 #define rson root<<1|1 #define Mid int mid=(l+r)>>1 #define FREI freopen("in.txt","r",stdin) #define N 30100 #define ll long long using namespace std; int n; ll ans[N<<2]; map<ll,int> invf; int a[N],pre[N]; ll f[N],res; struct que{ int l,r,id; }; que q[100100]; ll sum[100100]; void lisanhua(int n){ invf.clear(); f[0]=0; int cnt=1; for(int i=1;i<=n;i++){ if(!invf.count(a[i])){ invf[a[i]]=cnt; f[cnt++]=a[i]; } } } void update(int root,int l,int r,int ql,int qr,int val){ if(l>qr||r<ql) return; if(r<=qr&&l>=ql){ ans[root]=f[val]; return; } Mid; update(lson,l,mid,ql,qr,val); update(rson,mid+1,r,ql,qr,val); ans[root]=ans[lson]+ans[rson]; } void query(int root,int l,int r,int ql,int qr){ if(l>qr||r<ql) return; if(r<=qr&&l>=ql){ res+=ans[root]; return; } Mid; query(lson,l,mid,ql,qr); query(rson,mid+1,r,ql,qr); } bool cmp(que a,que b){ return a.r<b.r; } int main() { //FREI; int cas; for(scanf("%d",&cas);cas--;){ int n; scanf("%d",&n); Mem(pre,0); Mem(ans,0); for(int i=1;i<=n;i++) scanf("%d",&a[i]); lisanhua(n); int m; 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); int cnt=0; for(int i=1;i<=n;i++){ ll x=invf[a[i]]; update(1,1,n,i,i,x); if(pre[x]) update(1,1,n,pre[x],pre[x],0); pre[x]=i; while(q[cnt].r==i){ res=0; query(1,1,n,q[cnt].l,q[cnt].r); sum[q[cnt++].id]=res; } } for(int i=0;i<m;i++) printf("%lld\n",sum[i]); } }