HDU-1166-敌兵布阵-单点更新

83 阅读 0 评论 55 点赞

我是靠谱客的博主清爽外套，最近开发中收集的这篇文章主要介绍HDU-1166-敌兵布阵-单点更新，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166

这个题目是杭电1166的敌兵布阵，一道线段树的模板题；

嘿嘿，其实今天刚学的线段树，这也是我第一次写线段树，所以我的代码写了详细的注释；欢迎指正；

#include<iostream>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int ans=0;
struct node         //  利用结构体存储左右区间，以及所对应的权值；
{
    int l,r,v;
}node[200005];
//  建立线段树；
void build(int numb,int l,int r)    //  numb为父节点,l,r分别为左右儿子；
{
    int mid=(l+r)>>1;
    node[numb].l=l;
    node[numb].r=r;
    node[numb].v=0;     //  初始化为0；
    if(l==r) return;    //  节点长度为0，则就可以结束了；
    else{
        build(numb<<1,l,mid);       //  建立左儿子方向线段树；
        build(numb<<1|1,mid+1,r);   //  建立右儿子方向线段树；
    }
}
//  插入函数；
void Insert(int n,int d,int numb)   //  n为插入的权值，d为插入的点，numb为父节点；
{
    if(node[numb].l==node[numb].r&&node[numb].l==d){    //  左右儿子相等并且等于要插入的点，则说明找到了；
        node[numb].v+=n;            //  那么该节点的权值更新；
        return;
    }
    int mid=(node[numb].l+node[numb].r)>>1;
    if(d<=mid) Insert(n,d,numb<<1);                 //  d<=mid说明要找的节点在区间，则父节点为numb*2;
    else Insert(n,d,numb<<1|1);                     //  反之，在又区间，父节点为numb*2+1;
    node[numb].v=node[numb<<1].v+node[numb<<1|1].v; //  最后即便不是终层节点，也要更新数据；递归的真是巧妙啊；
}
//  查询函数；
void Search(int l,int r,int numb)   //  l,r为左右区间，numb为父节点；
{
    if(node[numb].l==l&&node[numb].r==r){   //  查找的左右区间和节点的左右区间刚好一致，说明找到了；
        ans+=node[numb].v;          //  说明就需要更新数据，加入新的权值；
        return;
    }
    int mid=(node[numb].l+node[numb].r)>>1;
    if(r<=mid) Search(l,r,numb<<1);         //  说明区间完全在改节点的左儿子区间内，则区间不变，父节点更新为下一层父节点；
    else if(l>mid) Search(l,r,numb<<1|1);   //  反之，则右区间；
    else{                                   //  都不符合，说明左右儿子都有区间，则需要分开查找；
        Search(l,mid,numb<<1);              //  注意需要将区间也分开；
        Search(mid+1,r,numb<<1|1);
    }
}
int main()
{
    cin.sync_with_stdio(false);
    int Case=1,t,n,temp;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        build(1,1,n);   //  建立线段树；1为起始的父节点；
        for(int i=1;i<=n;i++){
            scanf("%d",&temp);
            Insert(temp,i,1);   //  每存入一个数，则插入到线段树中，temp为权值，i为节点位置；
        }
        printf("Case %d:n",Case++);
        char ch[20];
        int a,b;
        while(~scanf("%s",&ch)){
            if(strcmp(ch,"End")==0) break;
            scanf("%d%d",&a,&b);
            if(strcmp(ch,"Add")==0) Insert(b,a,1);          //  增加人数，
            else if(strcmp(ch,"Sub")==0) Insert(-b,a,1);    //  减人数，直接加-b；
            else{
                ans=0;
                Search(a,b,1);  //  查询a,b区间；
                printf("%dn",ans);
            }
        }
    }
    return 0;
}