hdu 1166 敌兵布阵

74 阅读 0 评论 49 点赞

我是靠谱客的博主兴奋大白，这篇文章主要介绍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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#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;
}