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;
}
