学步园

小记：树状数组局限思维在N数组上，然后一直想不出如何得解。 后来百度了一下，别人都是对M数组排序然后用树状数组。我看了一下思路后，自己动手，然后代码正确，改成long long 就A了。

思路：此题是求某一段区间内不重复的数的总和。起初我是对N用树状数组，然后一直想不出如何得到解。 然后看了别人的思路，发现自己被自己局限住了。唉~这就是差距啊。对M用树状数组，先要去对M数组以每段的终点值进行排序，然后从第一个N数开始，如果该数之前没出现过，就放到树状数组的该位置上。如果之前出现过，那么将之前该数在树状数组上的位置上删掉，然后在树状数组的当前位置上加上该数，即相当于，每个数在树状数组上都是保存在它最后出现的那个位置上。 这样做的原因是，我们是一段一段M区间进行处理的。那么我们处理完到某一段末尾时，就可以给出该段的结果了。sum(r)
- sum(l-1)就是该段的结果。 这一点就是该做法的巧妙的地方。我们从1循环到n即可求出所有区间的answer。时间复杂度是O((N+M)logN)的样子，然后保存每一段的结果，最后输出即可。

每个数在之前是否出现过，用记录它在树状数组的位置的那个数组即可实现。只要不是初始值即代表出现过。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))

const int MAX_ = 1000010;
const int MAX = 50010;

struct node{
    int l,r;
    int id;
}a[MAX*4];

int loc[MAX_];

long long C[MAX], ans[MAX*4];
int p[MAX];

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

void add(int x,int num){
    while(x < MAX){
        C[x] += num;
        x += lowbit(x);
    }
}

long long sum(int x){
    long long cnt = 0;
    while(x > 0){
        cnt += C[x];
        x -= lowbit(x);
    }
    return cnt;
}

int cmp(const node& p, const node& q){
    return p.r < q.r;
}

int main(){
    int T, n, m;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        mst(C,0);
        mst(loc,-1);
        for(int i = 1; i <= n; ++i){
        	scanf("%d",&p[i]);
        }
        scanf("%d",&m);
        for(int i = 0; i < m; ++i){
            scanf("%d%d",&a[i].l,&a[i].r);
            a[i].id = i;
        }
        sort(a,a+m,cmp);
        int s = 1;
        for(int i = 0; i < m; ++i){
            while(s <= a[i].r){
                if(loc[p[s]] == -1){
                    loc[p[s]] = s;
                    add(s,p[s]);
                }
                else {
                    int tmp = loc[p[s]];
                    add(tmp,-p[s]);
                    loc[p[s]] = s;
                    add(s,p[s]);
                }
                s++;
            }
            ans[a[i].id] = sum(a[i].r) - sum(a[i].l-1);
        }
        for(int i = 0; i < m; ++i){
        	printf("%I64d\n",ans[i]);
        }
    }
    return 0;
}