HDU 3874 Necklace 树状数组的应用 - JAVA

题意：有一些数，这些数中有重复的，问从[L,R]区间的和是多少，重复的数只能算一次。
思路：因为有多次询问，所以暴力的话肯定超时，又因为是区间求和问题，所以可以考虑用树状数组求。树状数组可以解决没有重复数的情况，因此这道题我们可以特殊处理一下。首先我们可以把所有的询问都存起来，然后对询问按右端点排序，然后每次询问，对于排序后的每次询问，我们只考虑到该区间的右端点，并且记录每个数最后出现的位置，若出现相同的数，则需要从该数的位置开始减去该数。
代码：
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N = 50010;
const int M = 200010;
int dit[N];
__int64 num[N];
__int64 ans[M];
struct interval{
int lp,rp,id;
}rr[M];
bool cmp(interval a,interval b){
if(a.rp == b.rp)
return a.lp < b.lp;
return a.rp < b.rp;
}
int inline lowbit(int x){
return x & (-x);
}
void inline update(int x,int add){
while(x < N){
num[x] += add;
x += lowbit(x);
}
}
__int64 inline sum(int x){
__int64 s = 0;
while(x > 0){
s += num[x];
x -= lowbit(x);
}
return s;
}

int main(){
int numcase;
map mp;
scanf("%d",&numcase);
while(numcase--){
int n,m;
scanf("%d",&n);
memset(dit,0,sizeof(dit));
for(int i = 1; i <= n; ++i){
scanf("%d",&dit[i]);
}
scanf("%d",&m);
for(int i = 0; i < m; ++i){
scanf("%d%d",&rr[i].lp,&rr[i].rp);
if(rr[i].rp < rr[i].lp)
swap(rr[i].lp,rr[i].rp);
rr[i].id = i;
}
sort(rr,rr+m,cmp);
memset(num,0,sizeof(num));
memset(ans,0,sizeof(ans));
mp.clear();
int rp = 1;
for(int i = 0; i < m; ++i){
while(rp <= rr[i].rp){
int x = dit[rp];
if(mp[x] != 0){
update(mp[x],-x);
}
update(rp,x);
mp[x] = rp;
rp++;
}
ans[rr[i].id] = sum(rr[i].rp) - sum(rr[i].lp - 1);
}
for(int i = 0; i < m; ++i){
printf("%I64d\n",ans[i]);
}

}
//system("pause");
return 0;
}