心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
和HDU 3874类似,只不过数字的范围大了不少,不能直接开数组记录每个数字最后出现的位置,使用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<=&& 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 阅读(396) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理