# notWork

Feb 19th, 2019
94
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. using namespace std;
4.
5. typedef long long ll;
6.
7. vector<ll> b;
8. vector<ll> a;
9.
10. ll curi = 0;
11.
12. ll sum(ll lb, ll rb, ll l, ll r, ll v){
13. if(lb == l && rb == r){
14. return b[v];
15. }
16. if(l <= (lb + rb)/2 && r >= (lb + rb)/2 + 1){
17. return max(sum(lb,(lb + rb)/2, l, (lb + rb)/2, 2 * v),sum((lb + rb)/2 + 1,rb, (lb + rb)/2 + 1, r, 2 * v + 1));
18. }else if(l <= (lb + rb) / 2){
19. return sum(lb,(lb + rb)/2, l, r, 2 * v);
20. }else{
21. return sum((lb + rb)/2 + 1,rb, l, r, 2 * v + 1);
22. }
23. }
24.
25. ll changeEl(ll lb, ll rb, ll which, ll to, ll v){
26. if(lb == rb){
27. b[v] += to;
28. return b[v];
29. }
30. if(which >= lb && which <= (lb + rb)/2){
31. b[v] = max(changeEl(lb,(lb + rb)/2,which,to,2*v),b[2*v + 1]);
32. return b[v];
33. }else{
34. b[v] = max(changeEl((lb + rb)/2 + 1, rb ,which,to,2*v + 1),b[2*v]);
35. return b[v];
36. }
37. }
38.
39. ll fill(ll lb, ll rb, ll v){
40. if(lb == rb){
41. b[v] = a[curi];
42. curi++;
43. return b[v];
44. }
45. b[v] = max(fill(lb, (lb+rb)/2, 2*v),fill((lb+rb)/2 + 1, rb, 2*v + 1));
46. return b[v];
47. }
48.
49. int main()
50. {
51. ll n,k;
52. cin >> n >> k;
53. a.resize(n);
54. b.resize(4*n + 1);
55. for(ll i = 0; i < n; i++){
56. cin >> a[i];
57. }
58. fill(0,a.size()-1, 1);
59. for(ll i = 0; i < k; i++){
60. ll x,y,z;
61. cin >> x;
62. if(x == 1){
63. cin >> y >> z;
64. changeEl(0, a.size() - 1, y-1, z, 1);
65. }
66. if(x == 2){
67. cin >> y;
68. cout << sum(0,a.size() - 1, 0, y-1, 1) << endl;
69. }
70. }
71. return 0;
72. }
RAW Paste Data