首页 > 代码库 > HDU 1166 敌兵布阵

HDU 1166 敌兵布阵

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

 

思路:线段树入门题。

 

代码:

  

#include <iostream>#include <cstring>#define MAXSIZE 500000using namespace std;struct node{    int l,r;    int sum;}tree[MAXSIZE*4];int num[MAXSIZE];void build(int root,int l,int r){    tree[root].r = r;    tree[root].l = l;            if(l==r)    {        tree[root].sum = num[l];        return;    }        int mid = (r+l)/2;        build(root*2,l,mid);    build(root*2+1,mid+1,r);    tree[root].sum = tree[root*2].sum + tree[root*2+1].sum;}void update(int root,int pos,int value){    if(tree[root].r==tree[root].l&&tree[root].r==pos)    {        tree[root].sum+=value;        return;    }        int mid = (tree[root].r+tree[root].l)/2;        if(pos<=mid)    {        update(root*2,pos,value);    }    else    {        update(root*2+1,pos,value);    }    tree[root].sum = tree[root*2].sum + tree[root*2+1].sum;}int query(int root,int l,int r){    if(r>=tree[root].r&&l<=tree[root].l)        return tree[root].sum;        int mid = (tree[root].r+tree[root].l)/2;        if(r<=mid)    {        return query(root*2,l,r);    }    else if(l>mid)    {        return query(root*2+1,l,r);    }    else    {        int a = query(root*2,l,mid);        int b = query(root*2+1,mid+1,r);        return a+b;    }}int main(){    int test;    int n;    char t[8];    scanf("%d",&test);    int a,b;//    freopen("data.txt","r",stdin);    for(int k=1;k<=test;k++)    {        scanf("%d",&n);                for(int i=1;i<=n;i++)        {            scanf("%d",num+i);        }                build(1,1,n);                printf("Case %d:\n",k);                while(scanf("%s",t)&&strcmp(t,"End")!=0)        {            scanf("%d %d",&a,&b);            if(strcmp(t,"Query")==0)            {                printf("%d\n",query(1,a,b));            }            else if(strcmp(t,"Add")==0)            {                update(1,a,b);            }            else if(strcmp(t,"Sub")==0)            {                update(1,a,-b);            }                    }            }    return 0;}

 

HDU 1166 敌兵布阵