fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. typedef long long lld;
  7. const int BSZ = 305;
  8.  
  9. lld sum(int a, int b, const vector<int>& v, const vector<lld>& bckt)
  10. {
  11. 	int l = a / BSZ;
  12. 	int r = b / BSZ - 1;
  13. 	lld ret = 0;
  14. 	while(l<=r){
  15. 		ret += bckt[l++];
  16. 	}
  17. 	for(int i = a / BSZ * BSZ; i < a; ++i){
  18. 		ret -= v[i];
  19. 	}
  20. 	for(int i = b / BSZ * BSZ; i <= b; ++i){
  21. 		ret += v[i];
  22. 	}
  23. 	return ret;
  24. }
  25.  
  26. int main()
  27. {
  28. 	ios_base::sync_with_stdio(false);
  29. 	cin.tie(0);
  30. 	int n, q;
  31. 	cin >> n >> q;
  32. 	vector<int> v(n + 1);
  33. 	vector<lld> bckt(n / BSZ + 1);
  34. 	for(int i = 1; i <= n; ++i){
  35. 		cin >> v[i];
  36. 		bckt[i / BSZ] += v[i];
  37. 	}
  38.  
  39. 	for(int i = 0; i < q; ++i){
  40. 		int x, y, a, b;
  41. 		cin >> x >> y >> a >> b;
  42. 		if(x > y) swap(x, y);
  43. 		cout << sum(x, y, v, bckt) << '\n';
  44. 		lld k = 1LL * v[a] - b;
  45. 		v[a] = b;
  46. 		bckt[a / BSZ] -= k;
  47. 	}
  48. }
Success #stdin #stdout 0s 3452KB
comments (?)
stdin
copy 
5 2
1 2 3 4 5
2 3 3 1
3 5 4 1
stdout
copy 
5
10
https://ideone.com/I7vkPa
sqrt decomposition
language:
C++14 (gcc 8.3)
created:
9 years 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!