fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cassert>
  5.  
  6. using namespace std;
  7.  
  8. #define BASE		131072
  9. #define MAX_N		100004
  10. #define LL			long long
  11.  
  12. LL tree[2 * BASE];
  13. LL inp[MAX_N];
  14.  
  15. int n, q;
  16.  
  17. LL get(int l, int r){
  18. 	l += BASE; r+= BASE;
  19. 	LL ret = 0;
  20.  
  21. 	while(l < r){
  22. 		if(l & 1) ret += tree[l++];
  23. 		if((r & 1) == 0) ret += tree[r--];
  24.  
  25. 		l /= 2; r /= 2;
  26. 	}
  27. 	if(l == r)
  28. 		ret += tree[l];
  29.  
  30. 	return ret;
  31. }
  32.  
  33. void update(int idx, LL v){
  34. 	idx += BASE;
  35.  
  36. 	while(1 <= idx){
  37. 		tree[idx] += v;
  38. 		idx /= 2;
  39. 	}
  40. }
  41.  
  42. int main(){
  43.  
  44. 	scanf("%d%d", &n, &q);
  45.  
  46. 	for(int i = 1; i <= n; i++){
  47. 		scanf("%lld", &inp[i]);
  48. 		update(i, inp[i]);
  49. 	}
  50.  
  51. 	for(int i = 0; i < q; i++){
  52. 		int l, r, idx; LL v; scanf("%d%d%d%lld", &l, &r, &idx, &v);
  53. 		printf("[%d, %d] idx == %d, v == %lld\n", l, r, idx, v);
  54. 		// assert(1 <= l && l <= n);
  55. 		// assert(1 <= r && r <= n);
  56. 		printf("%d\n", get(l, r));
  57. 		update(idx, v - inp[idx]);
  58. 		inp[idx] = v;
  59. 	}
  60.  
  61. 	return 0;
  62. }
Success #stdin #stdout 0s 5260KB
comments (?)
stdin
copy 
5 2

-2147483648 
2147483648 
-2147483648 
-2147483648 
2147483648

1 5 3 0
1 5 4 0
stdout
copy 
[1, 5] idx == 3, v == 0
-2147483648
[1, 5] idx == 4, v == 0
0
https://ideone.com/vF9ydA
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!