题目大意：

多组测试数据，给你一串数（50000个），每个数最大1,000,000，然后询问最多200,000次区间和。
但是有一个很麻烦的地方就是，一个区间里面，相同的数只能计算一次。

分析：

看似有相同的数只是一个很小的细节，但是这应该才是这道题的关键。
现在急于解决的一个问题就是，怎样让这些相同的数不被重复计算，比较感性的想法就是，这些数我只存一个，也就是第一个，后面再出现我就不存了。但是这样询问区间的时候必定会出现问题。
我的解决办法就是，把区间按照起点坐标从小到大排序，起点坐标相同的两个区间的先后顺序无所谓。按顺序依次访问。在访问区间 [ a , b ] 的时候就删掉 a 左面的点， 这个删掉的意思是，把 a 左面出现多次但是只记录了第一次的数右移到 a 的右边，也就是他第 k(k>1)次出现但是当时没有记录下来的位置。用哈希表实现。要是真的要算最差的时间复杂度，做哈希表就要50000*50001/2就该超时了，但是那样的数据实在是太bt了，所以我决定先打出来试一下。

代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 50500
#define maxm 200500
#define maxx 1005000

using namespace std;

long long int tree[maxn];
int n,m;
int my_hash[maxx];
int my_next[maxn]; 
int a[maxn];

long long int ans[maxm];
struct interval
{
    int s;
    int e;
    int w;
}inv[maxm];

int lowbit(int x)
{
    return x&(-x);
}

void add(int i,int x)//给i位置加上x 
{
    while(i<maxn)
    {
        tree[i]+=x;
        i+=lowbit(i);
    }
}
long long int sum(int x)
{
    if(x==0)return 0;
    long long int s=0;
    while(x>0)
    {
        s+=tree[x];
        x-=lowbit(x);
    }
    return s;
}

bool my_cmp(interval a,interval b)
{
    return a.s<b.s;
}

int main()
{
    int test;
    cin>>test;
    while(test--)
    {
        memset(my_hash,0,sizeof(my_hash));
        memset(my_next,0,sizeof(my_next));
        memset(tree,0,sizeof(tree));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(my_hash[a[i]]!=0)
            {
                int l=my_hash[a[i]];
                while(my_next[l]!=0)
                {
                    l=my_next[l];
                }
                my_next[l]=i;
            }
            else
            {
                my_hash[a[i]]=i;
                add(i,a[i]);
            }
        }
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&inv[i].s,&inv[i].e);
            inv[i].w=i;
        }
        sort(inv+1,inv+m+1,my_cmp);
        int t=1;
        for(int i=1;i<=m;i++)
        {
            for(;t<inv[i].s;t++)
            {

                if(my_next[my_hash[a[t]]]!=0)
                {
                    add(my_hash[a[t]],-a[t]);
                    my_hash[a[t]]=my_next[my_hash[a[t]]];
                    add(my_hash[a[t]],a[t]);
                }
            }
            ans[inv[i].w]=sum(inv[i].e)-sum(inv[i].s-1);
        }
        for(int i=1;i<=m;i++)
        {
            printf("%lld\n",ans[i]);
        }
    }
}

后记：

果然数据没有那么bt，很快ac了。
注意：
1.tree数组等要用 long long int 。
2.输入输出用 cin，cout 就超时了。

最后在重新总结一遍思路就是，按照某一特定顺序查询区间，同时一边查找，一边按照特定的规则增加数据到树状数组里面了，这样就可以使得按照顺序查询的区间得到的答案都是正确的，既重复的数字只计算了一次的区间和。