http://acm.hdu.edu.cn/showproblem.php?pid=3333

不错的题，想了非常久不知道怎么处理，并且答案没看懂，然后找个样例模拟下别人的代码立即懂了---以后看不懂的话就拿个样例模拟下别人的代码

举个样例：1 3 3 5 3 5

查询

a, 2 4

b, 2 5

最初是这么想的：对于a查询，倘若把第二个数第三个数变成1个3。那么到b查询，又出现了两个3，再做处理似乎还是O（n），并且假设先出现2,5查询，后出现2,4查询。那么还须要把删除的数补回来.....o(╯□╰)o，然后就陷入迷茫啊.......

题解：

1、把查询按区间右端点由小到大排列，就避免了“须要把删除的数补回来”，如上面的样例，a查询的时候删除的3，在b查询的时候仍须要删除，可是假设先b查询后a查询。b查询须要删除第二个数第三个数。a查询须要把第三个数补回来....

2、每查询到一个区间。确保以右端点为结束为止的前缀没有反复的数

详细看代码-----拿样例模拟下，。回头我一定重写一遍

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <iostream>

#include <cmath>

#include <map>

#include <set>

#include <queue>

using namespace std;

#define ls(rt) rt*2

#define rs(rt) rt*2+1

#define ll long long

#define ull unsigned long long

#define rep(i,s,e) for(int i=s;i<e;i++)

#define repe(i,s,e) for(int i=s;i<=e;i++)

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

#define IN(s) freopen(s,"r",stdin)

#define OUT(s) freopen(s,"w",stdout)

const int MAXN =  50000+100;

struct Query

{

    int l,r;

    int id;

    bool operator < (const Query &c)const

    {

        return r<c.r;

    }

}q[100000 + 100];

ll c[MAXN],ans[100000 + 100];

ll num[MAXN],bi[MAXN];

int last[MAXN];

int N;

inline int lowbit(int i){return i&(-i);}

void add(int x, int v)

{

    while(x<=N)

    {

        c[x]+=v;

        x+=lowbit(x);

    }

}

ll sum(int i)

{

    ll ret=0;

    while(i>0)

    {

        ret+=c[i];

        i-=lowbit(i);

    }

    return ret;

}

int main()

{

    //IN("hdu3333.txt");

    int ncase,Q;

    scanf("%d",&ncase);

    while(ncase--)

    {

        CL(c,0);CL(last,0);

        scanf("%d",&N);

        for(int i=1;i<=N;i++)

        {

            scanf("%I64d",&num[i]);

            bi[i]=num[i];

        }

        scanf("%d",&Q);

        for(int i=1;i<=Q;i++)

        {

            scanf("%d%d",&q[i].l,&q[i].r);

            q[i].id=i;

        }

        sort(q+1,q+1+Q);

        sort(bi+1,bi+1+N);

        int qu=1;

        for(int i=1;i<=N;i++)

        {

            int pos=lower_bound(bi+1,bi+1+N,num[i])-bi;

            if(!last[pos])

            {

                add(i,num[i]);

                last[pos]=i;

            }

            else

            {

                add(last[pos],-num[i]);

                add(i,num[i]);

                last[pos]=i;

            }

            while(q[qu].r == i && qu<=Q)

            {

                ans[q[qu].id]=sum(i)-sum(q[qu].l-1);

                qu++;

            }

        }

        for(int i=1;i<=Q;i++)

            printf("%I64d\n",ans[i]);

    }

    return 0;

}