敌兵布阵线段树

时间 2019-12-07 标签敌兵布阵线段树

敌兵布阵

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Descriptionhtml

Lily 特别喜欢养花，可是因为她的花特别多，因此照料这些花就变得不太容易。她把她的花依次排成一行，每盆花都有一个美观值。若是Lily把某盆花照料的好的话，这盆花的美观值就会上升，若是照料的很差的话，这盆花的美观值就会降低。有时，Lily想知道某段连续的花的美观值之和是多少，可是，Lily的算术不是很好，你能快速地告诉她结果吗？ios

Inputpost

	第一行一个整数T，表示有T组测试数据。
每组测试数据的第一行为一个正整数N(N<=50000)，表示Lily有N盆花。接下来有N个正整数，第i个正整数ai表示第i盆花的初始美观值(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，表示结束，这条命令在每组数据最后出现 每组数据的命令不超过40000条

Output测试

	对于第i组数据，首先输出"Case i:"和回车。 对于每一个"Query i j"命令，输出第i盆花到第j盆花的美观值之和。

Sample Inputui

9
7 9 8 4 4 5 4 2 7
Query 7 9
Add 4 9
Query 3 6
Sub 9 6
Sub 3 3
Query 1 9
End

Sample Outputspa

Case 1:

13
30
50

第一次写线段树写以前看了基神推荐的写线段树风格 dalao写的代码太漂亮了仰望高端玩家

模仿写了一波基本是照着dalao的风格和思路走的

#include <iostream>
#include <cstdio>

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

const int maxn=50005;
int sum[maxn<<2];

void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%d",&sum[rt]);
        return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);

}

void update(int p,int add,int l,int r,int rt)
{
    if(l==r)
    {
        sum[rt]+=add;
        return;
    }
    int m=(l+r)>>1;
    if(p<=m)
         update(p,add,lson);
    else
         update(p,add,rson);
    pushup(rt);

}

int query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R){
        return sum[rt];
    }
    int m=(l+r)>>1;
    int ret=0;
    if(L<=m)  ret+=query(L,R,lson);
    if(R>m)   ret+=query(L,R,rson);

    return ret;
}

using namespace std;
int main()
{
     //freopen("input.txt","r",stdin);
     int T,n;
     scanf("%d",&T);
     for(int cas=1;cas<=T;cas++)
     {
         printf("Case %d:\n",cas);
         scanf("%d",&n);
         build(1,n,1);

         char op[10];
         while(~scanf("%s",op))
         {
             if(op[0]=='E')  break;
             int a,b;
             scanf("%d%d",&a,&b);
             if(op[0]=='S')
             {
                 update(a,-b,1,n,1);
             }
             if(op[0]=='A')
             {
                 update(a,b,1,n,1);
             }
             if(op[0]=='Q')
             {
                 printf("%d\n",query(a,b,1,n,1));
             }

         }

     }
}

转载于:https://www.cnblogs.com/Hyouka/p/5709542.htmlcode

敌兵布阵 线段树

敌兵布阵线段树