hdu 1166 敌兵布阵

59 阅读 0 评论 39 点赞

我是靠谱客的博主兴奋大白，最近开发中收集的这篇文章主要介绍hdu 1166 敌兵布阵，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接如下所示：

Problem - 1166

这个题目大意就是维护一个序列，有三种操作，给第i个数加上一个数，给第i个数减去一个数（这个直接转化乘加上一个相反数就行），求区间和。

基本上等于是线段树裸题。

为啥要用线段树呢？如果不用会怎么样？加或者减是O(1)操作，求区间和是O(n)，题目里边n是50000，操作数的规模是40000，那么最坏的情况直接炸了。

如果是线段树的话，加减以及求和的复杂度都是O(logn)，这样就不会炸。

加或者减的时候就是点修改。

代码如下所示：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<algorithm>
#include<cstring>
#include<set>
#include<map>
#include<queue>
#include<string>
#include<cmath>

using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int MAXN=50005;
int add[MAXN<<2];// sub当成取相反数相加即可
int sum[MAXN<<2];

// 如果进行了累加 需要自底向上更新sum
void push_up(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}


void build(int l,int r,int rt){
    sum[rt]=0;
    if (l==r){
        scanf("%d",&sum[rt]);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    push_up(rt);
}

// temp和num分别是修改点和
void update(int l,int r,int rt,int temp,int num){
    if (l==r && l==temp){
        sum[rt]+=num;
        return;
    }
    int mid=(l+r)>>1;
    if (temp<=mid){
        update(lson,temp,num);
    }else{
        update(rson,temp,num);
    }
    push_up(rt);
}

int query(int a,int b,int l,int r,int rt){
    if (a<=l && b>=r){
        return sum[rt];
    }
    int ans=0;
    int mid=(l+r)>>1;
    if (a<=mid){
        ans+=query(a,b,lson);
    }
    if (b>mid){
        ans+=query(a,b,rson);
    }
    return ans;
}


int main()
{
    int T,n;
    char str[10];
    int a,b;
    scanf("%d",&T);
    for (int i = 1; i <= T; ++i) {
        memset(add,0,sizeof(add));
        scanf("%d",&n);
        build(1,n,1);
        printf("Case %d:n",i);
        while (true){
            scanf("%s",str);
            if (str[0]=='E') break;
            scanf("%d %d",&a,&b);
            if (str[0]=='A'){
                update(1,n,1,a,b);
            }else if (str[0]=='S'){
                update(1,n,1,a,-b);
            }else if (str[0]=='Q'){
                printf("%dn", query(a,b,1,n,1));
            }
        }
    }
    return 0;
}