敌兵布阵

单点更新和区间更新还是有一些区别的,应该注意!

【题目类型】线段树单点更新

&题意：

第一行一个整数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 表示结束，这条命令在每组数据最后出现;

每组数据最多有40000条命令

&题解：

线段树单点更新模板题

【时间复杂度】\(O(nlogn)\)

&代码：

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

#define lsn b,m,rt<<1

#define rsn m+1,e,rt<<1|1

const int maxn=50000+9;

int seg[maxn<<2];

int a[maxn];

inline void PushUp(int rt)

{

    //注意这: 一定是=  不是+=  因为在updata时 +=会错

    seg[rt]=seg[rt<<1]+seg[rt<<1|1];

//    seg[rt]+=seg[rt<<1]+seg[rt<<1|1];   错的

}

void Build(int b,int e,int rt)

{

    seg[rt]=0;

    if (b==e){

        seg[rt]=a[b];

        return;

    }

    int m=b+e>>1;

    Build(lsn);

    Build(rsn);

    PushUp(rt);

}

void Updata(int idx,int xx,int b,int e,int rt)

{

    if (b==e){

        seg[rt]+=xx;

        return ;

    }

    int m=b+e>>1;

    //这不用再像区间一样弄了  因为只有1个位置 所以if else就够了  不用if + if 了

    if (idx<=m)

        Updata(idx,xx,lsn);

    else

        Updata(idx,xx,rsn);

    PushUp(rt);

}

int Query(int l,int r,int b,int e,int rt)

{

    if (l<=b&&e<=r){

        return seg[rt];

    }

    int m=b+e>>1;

    int ans=0;

    if (l<=m)

        ans+=Query(l,r,lsn);

    if (m<r)

        ans+=Query(l,r,rsn);

    return ans;

}

int K;

int main()

{

    int T;

    scanf("%d",&T);

    while(T--){

        int n;

        scanf("%d",&n);

        for(int i=1;i<=n;i++)

            scanf("%d",&a[i]);

        Build(1,n,1);

        printf("Case %d:\n",++K);

        char op[33];

        int u,v;

        while(1){

            scanf("%s",op);

            if (op[0]=='E') break;

            scanf("%d%d",&u,&v);

            if (op[0]=='A')

                Updata(u,v,1,n,1);

            if (op[0]=='S')

                Updata(u,-v,1,n,1);

            if (op[0]=='Q')

                printf("%d\n",Query(u,v,1,n,1));

        }

    }

    return 0;

}

巴特西

HDU 1166 敌兵布阵(线段树单点更新)

敌兵布阵

最新文章

热门文章