CodeForces315B:线段树与区间更新

题目描述：

Sereja 拥有一个包含 n 个整数的数组 a1, a2, ..., an。他非常活跃，计划执行 m 次操作。这 m 次操作分为三种类型：

1. 将第 vi 个数组元素设置为 xi。即执行 avi = xi。
2. 将每个数组元素增加 yi。即对所有的 ai 执行 ai = ai + yi (1 ≤ i ≤ n)。
3. 在纸上写下第 qi 个数组元素的值。即查询 aqi 的值。

请帮助 Sereja 完成所有这些操作。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 10^5)，表示数组的长度和操作的数量。第二行包含 n 个用空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 10^9)，表示原始数组的内容。

接下来的 m 行描述了 m 次操作，第 i 行描述了第 i 次操作。每行的第一个整数 ti (1 ≤ ti ≤ 3) 表示操作类型。如果 ti = 1，则后跟两个整数 vi 和 xi (1 ≤ vi ≤ n, 1 ≤ xi ≤ 10^9)；如果 ti = 2，则后跟一个整数 yi (1 ≤ yi ≤ 10^4)；如果 ti = 3，则后跟一个整数 qi (1 ≤ qi ≤ n)。

输出

对于每次第三类操作，输出对应的 aqi 值。按照输入中查询出现的顺序输出结果。

样例

问题分析：此问题可以通过使用线段树来高效地处理区间更新和单点查询。

解决方案代码：

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1e5 + 100;
struct Node {
    int l, r, val;
} tree[maxn * 4];
int a[maxn];

void build(int root, int l, int r) {
    tree[root].l = l;
    tree[root].r = r;
    tree[root].val = 0;
    if (l == r) {
        tree[root].val = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(root <<1, l, mid);
    build(root <<1 | 1, mid + 1, r);
}

void pushdown(int root) {
    if (tree[root].val != 0) {
        tree[root <<1].val += tree[root].val;
        tree[root <<1 | 1].val += tree[root].val;
        tree[root].val = 0;
    }
}

void update(int root, int l, int r, int cur, int op) {
    if (l <= tree[root].l && r >= tree[root].r) {
        if (op == 2) tree[root].val += cur;
        else tree[root].val = cur;
        return;
    }
    pushdown(root);
    int mid = (tree[root].l + tree[root].r) >> 1;
    if (l <= mid) update(root <<1, l, r, cur, op);
    if (r > mid) update(root <<1 | 1, l, r, cur, op);
}

int query(int root, int pos) {
    if (tree[root].l == tree[root].r) {
        return tree[root].val;
    }
    pushdown(root);
    int mid = (tree[root].l + tree[root].r) >> 1;
    if (pos <= mid) return query(root <<1, pos);
    else return query(root <<1 | 1, pos);
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        build(1, 1, n);
        for (int i = 1; i <= m; i++) {
            int t;
            scanf("%d", &t);
            if (t == 1) {
                int pos, x;
                scanf("%d%d", &pos, &x);
                update(1, pos, pos, x, 1);
            } else if (t == 2) {
                int v;
                scanf("%d", &v);
                update(1, 1, n, v, 2);
            } else if (t == 3) {
                int pos;
                scanf("%d", &pos);
                printf("%d\n", query(1, pos));
            }
        }
    }
    return 0;
}