和HDU 3874類似，只不過數(shù)字的范圍大了不少，不能直接開數(shù)組記錄每個數(shù)字最后出現(xiàn)的位置，使用map<int,int>記錄。
以下是我的代碼：
#include<iostream>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kMaxn(30007);
const int kMaxm(100007);
struct Interval
{
int a,b;
int id;
};
bool operator<(const Interval &a,const Interval &b)
{
return (a.b<b.b);
}
int n,m,r[kMaxn];
Interval query[kMaxm];
long long bit[kMaxn],ans[kMaxm];
void Add(int x,int delta)
{
for(int i=x;i<=n;i+=lowbit(i))
bit[i]+=delta;
}
long long Sum(int x)
{
long long re(0);
for(int i=x;i>0;i-=lowbit(i))
re+=bit[i];
return re;
}
int main()
{
//freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&r[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&query[i].a,&query[i].b);
query[i].id=i;
}
// Input
sort(query+1,query+m+1);
memset(bit,0,sizeof(bit));
map<int,int> pos;
for(int i=1,j=1;i<=n && j<=m;i++)
{
Add(i,r[i]);
if(pos.count(r[i]))
Add(pos[r[i]],-r[i]);
pos[r[i]]=i;
while(i==query[j].b)
{
ans[query[j].id]=Sum(query[j].b)-Sum(query[j].a-1);
j++;
}
}
for(int i=1;i<=m;i++)
printf("%I64d\n",ans[i]);
}
return 0;
}
posted on 2011-08-01 18:36
lee1r 閱讀(426)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)據(jù)結構