2015
04-13

Necklace

Mery has a beautiful necklace. The necklace is made up of N magic balls. Each ball has a beautiful value. The balls with the same beautiful value look the same, so if two or more balls have the same beautiful value, we just count it once. We define the beautiful value of some interval [x,y] as F(x,y). F(x,y) is calculated as the sum of the beautiful value from the xth ball to the yth ball and the same value is ONLY COUNTED ONCE. For example, if the necklace is 1 1 1 2 3 1, we have F(1,3)=1, F(2,4)=3, F(2,6)=6.

Now Mery thinks the necklace is too long. She plans to take some continuous part of the necklace to build a new one. She wants to know each of the beautiful value of M continuous parts of the necklace. She will give you M intervals [L,R] (1<=L<=R<=N) and you must tell her F(L,R) of them.

The first line is T(T<=10), representing the number of test cases.
For each case, the first line is a number N,1 <=N <=50000, indicating the number of the magic balls. The second line contains N non-negative integer numbers not greater 1000000, representing the beautiful value of the N balls. The third line has a number M, 1 <=M <=200000, meaning the nunber of the queries. Each of the next M lines contains L and R, the query.

The first line is T(T<=10), representing the number of test cases.
For each case, the first line is a number N,1 <=N <=50000, indicating the number of the magic balls. The second line contains N non-negative integer numbers not greater 1000000, representing the beautiful value of the N balls. The third line has a number M, 1 <=M <=200000, meaning the nunber of the queries. Each of the next M lines contains L and R, the query.

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 <cstdio>
#include <string.h>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <set>
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);
}
while(x < N){
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<int,int> 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;
}

1. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

2. 博主您好，这是一个内容十分优秀的博客，而且界面也非常漂亮。但是为什么博客的响应速度这么慢，虽然博客的主机在国外，但是我开启VPN还是经常响应很久，再者打开某些页面经常会出现数据库连接出错的提示