HDOJ 1166 ---敌兵布阵

83 阅读 0 评论 55 点赞

我是靠谱客的博主英俊白羊，最近开发中收集的这篇文章主要介绍HDOJ 1166 ---敌兵布阵，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

今天刚刚学了线段树，原来还有点不理解，学习Yoangh学长的博客，感觉懂了它用数组构造树，和查询的整个过程

所以对我来说，这道题很好入门的题。

在代码前先介绍大神的线段树风格:

1： maxn是题目给的最大区间,而节点数要开4倍,确切的来说节点数要开大于maxn的最小2^x的两倍。

2：lson和rson分辨表示结点的左儿子和右儿子,由于每次传参数的时候都固定是这几个变量,所以可以用预定于比较方便的。

3：结合lson和rson的预定义可以很方便。

4：PushUP(int rt)是把当前结点的信息更新到父结点。

5：PushDown(int rt)是把当前结点的信息更新给儿子结点rt表示当前子树的根(root),也就是当前所在的结点。

代码：

#include<iostream>
using namespace std;
#define MAXN 51100
int cnt[MAXN*4];
void Build(int l,int r,int rt)//rt是数组cnt的下标，从根节点开始 
{
     if( l==r){
         scanf("%d",&cnt[rt]);
         return ;
     }
     int mid=(l+r)>>1;
     Build(l,mid,rt<<1);      //  rt<<1 = 2*rt; 
     Build(mid+1,r,rt<<1|1);    //rt<<1|1 = 2*rt+1 ;
     cnt[rt]=cnt[rt<<1]+cnt[rt<<1|1];
}
void Update(int i,int add,int l,int r,int rt)
{
     if( l==r){
         cnt[rt]+=add;
         return ;
     }
     int mid=(l+r)>>1;
     if(i<=mid)   Update(i,add,l,mid,rt<<1);
     else    Update(i,add,mid+1,r,rt<<1|1);
     cnt[rt]=cnt[rt<<1]+cnt[rt<<1|1];
}
int Query(int L,int R,int l,int r,int rt)
{
    if( L<=l&&R>=r)
        return cnt[rt];
    int sum=0;
    int mid=(l+r)>>1;
    if(L<=mid)   sum+=Query(L,R,l,mid,rt<<1);
    if(R>mid)    sum+=Query(L,R,mid+1,r,rt<<1|1); 
    return sum;
}
int main() 
{
    int i,t,n,c,l,r;
    char str[10];
    scanf("%d",&t);
    for( c=1; c<=t; c++){
         memset(cnt,0,sizeof(cnt));
         scanf("%d",&n);
         Build(1,n,1);
         printf("Case %d:n",c);
         while( true){
                scanf("%s",str);
                if( str[0]=='E')
                    break;//结束
                if( str[0]=='Q'){//查询
                    scanf("%d%d",&l,&r);
                    printf("%dn",Query(l,r,1,n,1));
                }
                else if( str[0]=='A'){//删减
                     scanf("%d%d",&i,&l);
                     Update(i,l,1,n,1);
                }
                else{
                     scanf("%d%d",&i,&l);
                     Update(i,-l,1,n,1);
                }
         }
    }
           
    return 0;
}