题意：给一个数组，每次查询输出区间内不重复数字的和。
这是3xian教主的题。
用前缀和的思想可以轻易求得区间的和，但是对于重复数字这点很难处理。在线很难下手，考虑离线处理。
将所有查询区间从右端点由小到大排序，遍历数组中的每个数字，每次将该数字上次出现位置的值在树状数组中改为0，再记录当前位置，在树状数组中修改为当前的数值。这样可以保证在接下来的查询中该数字只出现了一次。这是贪心的思想，只保留最可能被以后区间查询的位置。如果当前位置是某个查询区间的右端点，这时候就可以查询了。最后再根据查询区间的编号排序输出即可了。
注意树状数组查询0位置会出现死循环。
HDU上long long 需要使用I64d。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#define ll long long
#define MAXN 100005
using namespace std;
int n;
map<int,int> pos;
struct Segment
{
int num,left,right;
ll ans;
Segment(,,):num(a),left(b),right(c)
{
ans=;
}
bool operator <(const Segment &p) const
{
return right<p.right;
}
};
bool cmp(Segment a,Segment b)
{
return a.num<b.num;
}
struct BIT
{
ll dat[MAXN];
int lowbit(int x)
{
return -x&x;
}
void clear()
{
memset(dat,,sizeof(dat));
}
void add(int x,ll val)
{
while(x<=n)
{
dat[x]+=val;
x+=lowbit(x);
}
}
ll sum(int x)
{
ll s=;
)
{
s+=dat[x];
x-=lowbit(x);
}
return s;
}
void modify(int x,ll val)
{
) return ;
ll t=sum(x)-sum(x-);
add(x,-t+val);
}
};
int arr[MAXN];
vector<Segment> vec;
BIT tree;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
pos.clear();
; i<=n; ++i)
scanf("%d",&arr[i]);
int q;
scanf("%d",&q);
vec.clear();
; i<=q; ++i)
{
int x,y;
scanf("%d%d",&x,&y);
vec.push_back(Segment (i,x,y));
}
sort(vec.begin(),vec.end());
tree.clear();
,j=; i<=n&&j<vec.size(); ++i)
{
tree.modify(pos[arr[i]],);
tree.modify(i,arr[i]);
pos[arr[i]]=i;
while(j<vec.size()&&i==vec[j].right)
{
vec[j].ans=tree.sum(vec[j].right)-tree.sum(vec[j].left-);
j++;
}
}
sort(vec.begin(),vec.end(),cmp);
; i<vec.size(); ++i)
printf("%I64d\n",vec[i].ans);
}
;
}