计算区间内的值的时候如果两个值相等，只能计算其中一个。
这道题需要将所有的问题输入之后再计算，首先，对所有问题的右边界进行排序。从左到有依次插入数组中的数据，并记录数据的位置，如果该数据之前记录过，在重新记录时需要将之前记录的数据修改为0。一边插入数据，一边还要比较i和记录的问题的右边界，如果i大于等于当前问题的右边界，计算当前问题的值，并记录在ans数组里面，记录之后开始检查下一个问题。到最后，所有数据都记录之后，重新一起输出。
1A！
#include#include #include #define N 200005 struct node { int x,y; __int64 sum; }a[N]; struct Q { int x,y; int id; }q[N]; int b[N]; int mark[N*5]; void CreatTree(int t,int x,int y) { a[t].x=x; a[t].y=y; a[t].sum=0; if(x==y) return ; int mid=(x+y)/2; int temp=t*2; CreatTree(temp,x,mid); CreatTree(temp+1,mid+1,y); return ; } void InsertTree(int t,int x,int k) { if(a[t].x==a[t].y) { a[t].sum+=k; return ; } int temp=t*2; int mid=(a[t].x+a[t].y)/2; if(x<=mid) InsertTree(temp,x,k); else InsertTree(temp+1,x,k); a[t].sum=a[temp].sum+a[temp+1].sum; return ; } __int64 FindTree(int t,int x,int y) { __int64 ans; ans=0; if(a[t].x==x&&a[t].y==y) return a[t].sum; int temp=t*2; int mid=(a[t].x+a[t].y)/2; if(y<=mid) ans=FindTree(temp,x,y); else if(x> mid) ans=FindTree(temp+1,x,y); else { ans+=FindTree(temp,x,mid); ans+=FindTree(temp+1,mid+1,y); } return ans; } int cmp(const void *a,const void *b) { return (*(Q *)a).y-(*(Q *)b).y; } __int64 ans[N]; int main() { int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); CreatTree(1,1,n); int i; for(i=1;i<=n;i++) scanf("%d",&b[i]); int m; scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d%d",&q[i].x,&q[i].y); q[i].id=i; } qsort(q+1,m,sizeof(q[0]),cmp); int k; k=1; memset(mark,0,sizeof(mark)); for(i=1;i<=n;i++) { int flag; flag=mark[b[i]]; if(flag) InsertTree(1,flag,-b[i]); InsertTree(1,i,b[i]); mark[b[i]]=i; while(q[k].y<=i&&k<=m) { ans[q[k].id]=FindTree(1,q[k].x,q[k].y); k++; } } for(i=1;i<=m;i++) printf("%I64d\n",ans[i]); } return 0; }