11569: 【原1569】二哥的军训

题目描述

author: DarkFlameMaster 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1569 # Description 交大的女生们这段时间正在进行军训，所以一直渴望联谊的二哥又开始忙乎了。交大一共有N个女生连,为了撩到最合自己口味的女生，二哥一直密切关注着这些女生连的活动情况。由于事先买通了所有的纠纠，每个女生连单身女生的人数二哥都掌握的一清二楚,虽然这些人数都有可能发生变动，可能有女生脱单了或是又分了手,但这些都逃不过二哥的情报网。

二哥要选择每天的联谊对象,所以他随时得知道某一段连续的女生连一共有多少个单身女生。但女生们的感情状况经常波动，而二哥每次查询的女生连也都不一样，由于还要花时间撩妹，他不可能一个一个连去数。好在二哥学过树状数组，他决定写一个程序帮助自己解决这个问题。

Input Format

第一行有一个整数N ，表示有N个女生连，编号为1-N。

第二行有N个正整数，分别代表军训开始时每个女生连单身女生的数目。

接下来每行有一条纠纠送来的情报，情报有4种形式：

inc x y ，x和y为正整数,表示编号为x的女生连新增了y名单身女生；
dec x y ，x和y为正整数,表示编号为x的女生连减少了y名单身女生；
query x y ，x和y为正整数,x<=y，表示询问第x到第y个女生连的总单身人数；
end ，表示结束，这条命令仅在所有情报最后出现一次。

Output Format

对于每个query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。

Sample Input

10
1 2 3 4 5 6 7 8 9 10
query 1 3
inc 3 6
query 2 7
dec 10 2
inc 6 3
query 3 10
end

Sample Output

6
33
59

Sample Input

6
13 24 20 8 14 29
query 4 5
inc 1 3
query 1 1
dec 6 4
query 2 6
query 6 6
end

Sample Output

Limits

对于100%的数据，1<=N<=10000，且保证每个数据不超过int范围。
请使用树状数组进行解题。

yyong119's solution

#include <iostream>
using namespace std;
const int MAX_N = 10010;
struct node {
    int l, r, key;
}tree[MAX_N << 1];

void buildtree(int node, int l, int r) {

    if (l == r) {
        tree[node].l = l; tree[node].r = r;
        cin >> tree[node].key;
        return;
    }
    int mid = (l + r) >> 1;
    buildtree(node << 1, l, mid);
    buildtree(node << 1 | 1, mid + 1, r);
    tree[node].l = l; tree[node].r = r;
    tree[node].key = tree[node << 1].key + tree[node << 1 | 1].key;
}

void inc(int node, int pos, int key) {

    if (tree[node].l == tree[node].r) {
        tree[node].key += key;
        return;
    }
    int mid = (tree[node].l + tree[node].r) >> 1;
    if (pos > mid) inc(node << 1 | 1, pos, key);
    else inc(node << 1, pos, key);
    tree[node].key = tree[node << 1].key + tree[node << 1 | 1].key;
}

void dec(int node, int pos, int key) {

    if (tree[node].l == tree[node].r) {
        tree[node].key -= key;
        return;
    }
    int mid = (tree[node].l + tree[node].r) >> 1;
    if (pos > mid) dec(node << 1 | 1, pos, key);
    else dec(node << 1, pos, key);
    tree[node].key = tree[node << 1].key + tree[node << 1 | 1].key;
}

int query(int node, int l, int r) {

    if (tree[node].l == l && tree[node].r == r) return tree[node].key;
    int mid = (tree[node].l + tree[node].r) >> 1;
    if (l > mid) return query(node << 1 | 1, l, r);
    else if (r <= mid) return query(node << 1, l, r);
    else return query(node << 1, l, mid) + query(node << 1 | 1, mid + 1, r);
}

int main() {

    ios::sync_with_stdio(false);
    int n; cin >> n;
    buildtree(1, 1, n);
    while (true) {

        int tmp1, tmp2; char op[10];
        cin >> op;
        if (op[0] == 'e') break;
        cin >> tmp1 >> tmp2;
        switch (op[0]) {
            case 'i':
                inc(1, tmp1, tmp2);
                break;
            case 'd':
                dec(1, tmp1, tmp2);
                break;
            case 'q':
                cout << query(1, tmp1, tmp2) << endl;
                break;
        }
    }
    return 0;
}