线段树专题训练

ゝ一纸荒年。 2023-07-09 05:25 4阅读 0赞

###  ###

*  【HDU】1166 - 敌兵布阵

# 【HDU】1166 - 敌兵布阵 #

> 原题链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1166][http_acm.hdu.edu.cn_showproblem.php_pid_1166]

**题意：** 第一行一个整数 T，表示有 T 组数据。  
每组数据第一行一个正整数 N（N<=50000），表示敌人有 N 个工兵营地，接下来有 N 个正整数，第 i 个正整数 ai 代表第 i 个工兵营地里开始时有 ai 个人（1 <= ai <= 50）。  
接下来每行有一条命令，命令有 4 种形式：  
(1) Add i j，i 和 j 为正整数，表示第 i 个营地增加 j 个人（ j 不超过30）  
(2)Sub i j ，i 和 j 为正整数，表示第 i 个营地减少 j 个人（ j 不超过30）  
(3)Query i j ，i 和 j 为正整数，i <= j，表示询问第i到第 j 个营地的总人数  
(4)End 表示结束，这条命令在每组数据最后出现

**思路：** 线段树经典题目，当然也是树状数组裸题。记得加上iios::sync\_with\_stdio(0); ，卡时间点，要不然就用scanf，printf。

**Code：**

#include <iostream>
    #include <cstring>
    using namespace std;
    const int N = 5e4+100;
    int a[N];
    char str[10];
    struct node{ 
        int l,r,m;
    }tree[N<<2];
    void build_tree(int node,int l,int r){ 
        tree[node].l=l, tree[node].r=r;
        if(l==r){ 
            tree[node].m=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build_tree(node<<1,l,mid);
        build_tree(node<<1|1,mid+1,r);
        tree[node].m=tree[node<<1].m+tree[node<<1|1].m;
    }
    int query(int node,int l,int r){ 
        if(tree[node].l==l && tree[node].r==r)
            return tree[node].m;
        int mid=(tree[node].l+tree[node].r)>>1;
        if(r<=mid)  return query(node<<1,l,r);
        else if(l>mid)   return query(node<<1|1,l,r);
        else return query(node<<1,l,mid)+query(node<<1|1,mid+1,r);
    }
    void add(int node,int i,int j){ 
        if(tree[node].l==tree[node].r){ 
            tree[node].m+=j;
            return;
        }
        else{ 
            tree[node].m+=j;
            if(i<=tree[node<<1].r)  add(node<<1,i,j);
            else    add(node<<1|1,i,j);
        }
    }
    int main(){ 
        ios::sync_with_stdio(0);
        int t;  cin>>t;
        for(int k=1;k<=t;k++){ 
            int n;  cin>>n;
            for(int i=1;i<=n;i++)
                cin>>a[i];
            cout<<"Case "<<k<<":"<<endl;
            build_tree(1,1,n);
    
            while(cin>>str){ 
                if(!strcmp(str,"End"))  break;
                int i,j;    cin>>i>>j;
                if(!strcmp(str,"Add"))
                    add(1,i,j);
                if(!strcmp(str,"Sub"))
                    add(1,i,-j);
                if(!strcmp(str,"Query"))
                    cout<<query(1,i,j)<<endl;
            }
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1166]: http://acm.hdu.edu.cn/showproblem.php?pid=1166