这道题目和我之前做过的一道3xian大牛出的题目很像，不过总的来说还是要简单一点儿。
计算区间内的值的时候如果两个值相等，只能计算其中一个。
这道题需要将所有的问题输入之后再计算，首先，对所有问题的右边界进行排序。从左到有依次插入数组中的数据，并记录数据的位置，如果该数据之前记录过，在重新记录时需要将之前记录的数据修改为0。一边插入数据，一边还要比较i和记录的问题的右边界，如果i大于等于当前问题的右边界，计算当前问题的值，并记录在ans数组里面，记录之后开始检查下一个问题。到最后，所有数据都记录之后，重新一起输出。
1A！
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#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
",ans[i]);
}
return 0;
}