树状数组的应用。
采用离线算法：先按询问的右端点排序，然后依次把数字插入到树状数组里面，pos[i]记录数字i上一次在数组里面出现的位置，如果i已经出现过，删除之前的，添加到当前的位置。遇到可以处理的询问则处理，同时存储结果。
以下是我的代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kMaxn(50007);
const int kMaxm(200007);
const int kMaxv(1000007);
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];
int pos[kMaxv];
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));
memset(pos,-1,sizeof(pos));
for(int i=1,j=1;i<=n && j<=m;i++)
{
Add(i,r[i]);
if(pos[r[i]]!=-1)
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 11:56
lee1r 阅读(549)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数据结构