hdu 1166 敌兵布阵（单点更新，区间查询）

题意：

N个工兵营地。工兵营地里的人数分别为：a1,a2,....aN

Add i,j：第i个工兵营地里增加j人

Sub i,j：第i个工兵营地里减少j人

Query i,j：查询第i个第j个工兵营地共有多少人

思路：

线段树、树状数组都可以做，看代码

代码：

线段树：

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;

}

int main(){

    int T,n;

    scanf("%d",&T);

    for(int t=1;t<=T;++t){

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

        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] == 'A') update(a,b,1,n,1);

            else if(op[0] == 'S') update(a,-b,1,n,1);

            else if(op[0] == 'Q') printf("%d\n",query(a,b,1,n,1));

        }

    }

}

树状数组：

int n;

int a[50005];

int C[50005];

void init(){

    rep(i,1,n){

        C[i]=0;

        for(int j=i-lowbit(i)+1;j<=i;j++){

                C[i]+=a[j];

        }

    }

}

void add(int x,int y){

    for(int i=x;i<=n;i+=lowbit(i)){

        C[i]+=y;

    }

}

int calc(int x){

    if(x==0) return 0;

    int ans=0;

    for(int i=x;i>0;i-=lowbit(i))

        ans+=C[i];

    return ans;

}

int query(int x,int y){

    return calc(y)-calc(x-1);

}

int main(){

    int T;

    cin>>T;

    rep(t,1,T){

        scanf("%d",&n);

        rep(i,1,n){

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

        }

        init();

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

        char ope[10];

        while(1){

            scanf("%s",ope);

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

            int x,y;

            if(ope[0]=='A'){

                scanf("%d%d",&x,&y);

                add(x,y);

            }

            else if(ope[0]=='S'){

                scanf("%d%d",&x,&y);

                add(x,-y);

            }

            else{

                scanf("%d%d",&x,&y);

                int ans=query(x,y);

                printf("%d\n",ans);

            }

        }

    }

    return 0;

}

巴特西

hdu 1166 敌兵布阵（单点更新，区间查询）

最新文章

热门文章