hdoj--1166 敌兵布阵(树状数组or线段树)

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define Avg(x, y) ((x & y) + ((x ^ y) >> 1))

const int maxn = 50000 + 5;
int tree[3 * maxn];
int n, t;

void build(int l, int r, int num){
    if(l == r){
        scanf("%d", &tree[num]);
        return;
    }
    int mid = Avg(l, r);
    build(l, mid, num << 1);
    build(mid + 1, r, num << 1 | 1);

    tree[num] = tree[num << 1] + tree[num << 1 | 1];
}

void update(int l, int r, int num, int pos, int val){
    if(l == r){
        tree[num] += val;
        return;
    }
    int mid = Avg(l, r);
    if(pos <= mid) update(l, mid, num << 1, pos, val);
    else  update(mid + 1, r, num << 1 | 1, pos, val);

    tree[num] = tree[num << 1] + tree[num << 1 | 1];
}

int query(int l, int r, int L, int R, int num){
    if(L <= l && r <= R) return tree[num];
    int mid = Avg(l, r);
    int ret = 0;
    if(L <= mid) ret += query(l, mid, L, R, num << 1);
    if(R > mid) ret += query(mid + 1, r, L, R, num << 1 | 1);

    return ret;
}

int main(){
#ifdef EXMY
freopen("data.in", "r", stdin);
#endif // EXMY

    scanf("%d", &t);
    for(int Case = 1; Case <= t; ++Case){
        printf("Case %d:n", Case);
        memset(tree, 0, sizeof(tree));

        scanf("%d", &n);
        build(1, n, 1);

        char op[10];
        int x, y;
        while(scanf("%s", op) && op[0] != 'E'){
            if(op[0] == 'A'){
                scanf("%d %d", &x, &y);
                update(1, n, 1, x, y);
            }
            else if(op[0] == 'S'){
                scanf("%d %d", &x, &y);
                update(1, n, 1, x, -y);
            }
            else if(op[0] == 'Q'){
                scanf("%d %d", &x, &y);
                printf("%dn", query(1, n, x, y, 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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 50000 + 5;
int n, t;
int c[maxn];
int lowbit(int x) {
    return x & -x;
}
void add(int x, int v) {
    for(int i = x; i <= n; i += lowbit(i))
        c[i] += v;
}
int sum(int x) {
    int s = 0;
    for(int i = x; i ; i -= lowbit(i))
        s += c[i];
    return s;
}

int main() {
#ifdef EXMY
freopen("data.in", "r", stdin);
#endif // EXMY

    scanf("%d", &t);
    for(int Case = 1; Case <= t; ++Case){
        printf("Case %d:n", Case);
        memset(c, 0, sizeof(c));

        scanf("%d", &n);
        int a;
        for(int i = 1; i <= n; ++i){
            scanf("%d", &a);
            add(i, a);
        }
        char op[10];
        int x, y;

        while(scanf("%s", op) && op[0] != 'E'){
            if(op[0] == 'A'){
                scanf("%d %d", &x, &y);
                add(x, y);
            }
            else if(op[0] == 'S'){
                scanf("%d %d", &x, &y);
                add(x, -y);
            }
            else if(op[0] == 'Q'){
                scanf("%d %d", &x, &y);
                printf("%dn", sum(y) - sum(x - 1));
            }
        }
    }
    return 0;
}