树状数组求区间内不同元素和
离线考虑，把询问区间按右端点排序，记录每个数上一次出现的位置，如果已经出现过，把上一个删掉，当前的加进去，即只留下最近的一个元素。

Necklace

2
6
1 2 3 4 3 5
3
1 2
3 5
2 6
6
1 1 1 2 3 5
3
1 1
2 4
3 5

3
7
14
1
3
6

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long int LL;

struct ASK
{
    int l,r,id;
}ask[200100];

int n,q;
int pre[1000100];
LL tree[50100],val[50100],ans[200100];

bool cmp(ASK a,ASK b)
{
    if(a.r!=b.r) return a.r<b.r;
    return a.l<b.l;
}

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

void ADD(int p,int v)
{
    for(int i=p;i<=n+10;i+=lowbit(i)) tree[i]+=v;
}

LL SUM(int p)
{
    LL sum=0;
    for(int i=p;i;i-=lowbit(i)) sum+=tree[i];
    return sum;
}

int main()
{
    int TAT;
    scanf("%d",&TAT);
while(TAT--)
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%I64d",&val[i]);
    scanf("%d",&q);
    for(int i=0;i<q;i++)
    {
        scanf("%d%d",&ask[i].l,&ask[i].r);
        ask[i].id=i;
    }

    sort(ask,ask+q,cmp);
    memset(tree,0,sizeof(tree));
    memset(pre,-1,sizeof(pre));

    int cur=1;
    for(int i=0;i<q;i++)
    {
        while(cur<=ask[i].r)
        {
            int x=val[cur];
            if(pre[x]!=-1)
            {
                ADD(pre[x],-x);
            }
            ADD(cur,x);
            pre[x]=cur++;
        }
        ans[ask[i].id]=SUM(ask[i].r)-SUM(ask[i].l-1);
    }
    for(int i=0;i<q;i++)
        printf("%I64d\n",ans[i]);
}
    return 0;
}

HDOJ 3874 Necklace,布布扣,bubuko.com

HDOJ 3874 Necklace

原文：http://blog.csdn.net/u012797220/article/details/22149471