樹狀數(shù)組的應用。
采用離線算法：先按詢問的右端點排序，然后依次把數(shù)字插入到樹狀數(shù)組里面，pos[i]記錄數(shù)字i上一次在數(shù)組里面出現(xiàn)的位置，如果i已經出現(xiàn)過，刪除之前的，添加到當前的位置。遇到可以處理的詢問則處理，同時存儲結果。
以下是我的代碼：
#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 閱讀(585)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)據(jù)結構