CodeForces - 315B
|
Time Limit: 1000MS |
|
Memory Limit: 262144KB |
|
64bit IO Format: %I64d & %I64u |
Submit Status
Description
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.
Help Sereja, complete all his operations.
Input
The first line contains integers n, m(1 ≤ n, m ≤ 105).
The second line contains n space-separated integers a1, a2, ..., an(1 ≤ ai ≤ 109) —
the original array.
Next m lines describe operations, the i-th line describes the i-th operation.
The first number in the i-th line is integer ti(1 ≤ ti ≤ 3) that
represents the operation type. If ti = 1, then it is followed by two integers vi and xi, (1 ≤ vi ≤ n, 1 ≤ xi ≤ 109).
If ti = 2, then it is followed by integer yi(1 ≤ yi ≤ 104).
And if ti = 3, then it is followed by integer qi(1 ≤ qi ≤ n).
Output
For each third type operation print value aqi. Print the values in the order, in which the corresponding queries
follow in the input.
Sample Input
Input
10 11
1 2 3 4 5 6 7 8 9 10
3 2
3 9
2 10
3 1
3 10
1 1 10
2 10
2 10
3 1
3 10
3 9
Output
2
9
11
20
30
40
39
这道题目大家须要思考，不要一看到题目就用线段树，要想想有没有更好的方法，这里的题目给出的三种操作
能够知道没有一个是对区间进行操作的，唯一一个都是对整个数组操作。对全部的数的影响一样。
所以代码便能够变为例如以下：
/*
Author: 2486
Memory: 204 KB Time: 93 MS
Language: GNU G++11 4.9.2 Result: Accepted
VJ RunId: 4206974 Real RunId: 12270208
Public: No Yes
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
int n,m,p,c,v,a[maxn];
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
}
int cnt=0;
while(m--) {
scanf("%d%d",&p,&c);
if(p==1) {
scanf("%d",&v);
a[c]=v-cnt;
} else if(p==2) {
cnt+=c;
} else {
printf("%d\n",a[c]+cnt);
}
}
return 0;
}
|
