首页 > 其他 > 详细

hdu 1166 敌兵布阵_线段树

时间:2014-02-22 05:47:47      阅读:313      评论:0      收藏:0      [点我收藏+]

题意:略

思路:这题是单点更新,如果是减少的话,直接把数据变成负加上去就行了。

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 50010
int n,ans;
struct{
    int l,r,value;
}tree[MAXN<<2];
void Build(int l,int r,int id){
    tree[id].l=l;
    tree[id].r=r;
    tree[id].value=0;
    if(l!=r){
        int mid=(l+r)>>1;
        Build(l,mid,id<<1);
        Build(mid+1,r,id<<1|1);
    }
}
void update(int l,int value,int id){
    if(tree[id].l==tree[id].r&&tree[id].l==l){
        tree[id].value+=value;
        return;
    }
    int mid=(tree[id].l+tree[id].r)>>1;
    if(l<=mid)
        update(l,value,id<<1);
    else
        update(l,value,id<<1|1);
    tree[id].value=tree[id<<1].value+tree[id<<1|1].value;
}
void query(int l,int r,int id){
    if(tree[id].l==l&&tree[id].r==r){
        ans+=tree[id].value;
        return;
    }
    int mid=(tree[id].l+tree[id].r)>>1;
    if(r<=mid)
        query(l,r,id<<1);
    else if(l>mid)
        query(l,r,id<<1|1);
    else{
        query(l,mid,id<<1);
        query(mid+1,r,id<<1|1);
    }
}
int main(int argc, char** argv) {
    int Cas=1,t,x,y,n,i,value;
    char str[20];
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        Build(1,n,1);
        for(i=1;i<=n;i++){
            scanf("%d",&value);
            update(i,value,1);
        }
        printf("Case %d:\n",Cas++);
        while(scanf("%s",str),strcmp(str,"End")){
            scanf("%d%d",&x,&y);
            if(strcmp(str,"Add")==0)update(x,y,1);
            else if(strcmp(str,"Sub")==0)update(x,-y,1);
            else{
                ans=0;
                query(x,y,1);
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}


hdu 1166 敌兵布阵_线段树

原文:http://blog.csdn.net/neng18/article/details/19631387

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!