HDU--3333(树状数组+离线处理）

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<set>
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxd=30000+10;
const int maxn=100000+5;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1 | 1
typedef long long ll;
typedef pair<int,int> pii;
#define eps 1e-10

using namespace std;
//---------------------
typedef long long ll;
int a[maxd];
ll c[maxd];
int op,n,l,r;
struct node
{
    int l,r;
    int id;
    ll _sum;
    bool operator<(node a) const
    {
        if(r!=a.r)
            return r<a.r;
        return l<a.l;
    }
};
node qq[maxn];
ll ans[maxn];
map<int,int> vis;

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

ll sum(int x)
{
    ll ret=0;
    while(x>0)
    {
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}

void add(int x,int d)
{
    while(x<=n)
    {
        c[x]+=d;
        x+=lowbit(x);
    }
}

int main()
{
    int kase;
    freopen("1.txt","r",stdin);
    scanf("%d",&kase);
    while(kase--)
    {
        scanf("%d",&n);

        mem(c,0);
        vis.clear();
        for(int i=1; i<=n; ++i)
            scanf("%d",&a[i]);

        scanf("%d",&op);
        for(int i=1; i<=op; ++i)
            scanf("%d %d",&qq[i].l,&qq[i].r),qq[i].id=i;
        sort(qq+1,qq+1+op);
        qq[0].l=0,qq[0].r=0;
        for(int i=1; i<=op; ++i)
        {
            int ll=qq[i].l,rr=qq[i].r;

            for(int j=qq[i-1].r+1; j<=qq[i].r; ++j)
            {
                if(vis.find(a[j])!=vis.end())
                {
                    add(vis[a[j]],-a[j]);
                }
                add(j,a[j]);
                vis[a[j]]=j;
            }
          
            ans[qq[i].id]=sum(rr)-sum(ll-1);
        }
        for(int i=1; i<=op; ++i)
            printf("%lld\n",ans[i]);
    }
    return 0;
}