地址
B. Sereja and Array
time limit per test 1 second
memory limit per test 256 megabytes
input standard input
output standard output
Sereja has got an array, consisting of n integers, a1, a2, ..., an. Sereja is an active boy, so he is now going to complete m operations. Each operation will have one of the three forms:
Make vi-th array element equal to xi. In other words, perform the assignment avi = xi.
Increase each array element by yi. In other words, perform n assignments ai = ai + yi (1 ≤ i ≤ n).
Take a piece of paper and write out the qi-th array element. That is, the element aqi.
给N个元素的数组， 有三种操作 1 是把第i个元素变成v， 2是所有元素都加V， 3 询问第i个元素的值。
我用了树状数组，理论上用线段树也可以做，但树状数组明显要好写点，感觉还要比线段树快些。
树状数组原本用来就区间的和，只要稍微改进一下就和更新点，求点的值， 我们如果更新点x为v（当原来点是0事） 我们update（x , v） 和 update(x, -v) ， 这样我们求1到x的和是求到的就是x点的值。
//cf 315 B Sereja and Array //2013-06-13-20.02 #include <stdio.h> #include <string.h> const int maxn = 100005; int a[maxn]; int n; inline int lowbit(int x) { return x&-x; } int update(int x, int v) { while (x <= n+1) { a[x] += v; x += lowbit(x); } return 0; } int getsum(int x) { int sum = 0; while (x) { sum += a[x]; x -= lowbit(x); } return sum; } int main() { int m; while (scanf("%d %d", &n, &m) != EOF) { memset(a, 0, sizeof(a)); int t, op, x, v; for (int i = 1; i <= n; i++) { scanf("%d", &t); update(i, t); update(i+1, -t); } while (m--) { scanf("%d", &op); if (op == 1) { scanf("%d %d", &x, &v); int tmp = getsum(x); update(x, -tmp); update(x+1, tmp); update(x, v); update(x+1, -v); } else if (op == 2) { scanf("%d", &v); update(1, v); } else { scanf("%d", &x); printf("%d\n", getsum(x)); } } } return 0; }
