fork(5) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long t,n,m,u,v,k,c;
  6. long long tree[500000];
  7. long long lazytree[500000];
  8.  
  9. void Build(long long index, long long start, long long end);
  10. long long Query(long long index, long long start, long long end, long long range_start, long long range_end);
  11. void MarkChild(long long index, long long start, long long end);
  12. long long update(long long index, long long start, long long end, long long range_start, long long range_end, long long value);
  13.  
  14. int main(){
  15. 	ios_base::sync_with_stdio(false);
  16. 	cin.tie(0);
  17. 	cin >> t;
  18. 	while(t--){
  19. 		cin >> n >> c;
  20. 		Build(0, 0, n-1);
  21. 		for(int i = 0; i < c; ++i){
  22. 			cin >> k;
  23. 			if(k==0){
  24. 				cin >> u >> v >> m;
  25. 				--u,--v;
  26. 				update(0, 0, n-1LL, u, v, m);
  27. 			}
  28. 			else{
  29. 				cin >> u >> v;
  30. 				cout << Query(0, 0, n-1LL, u-1LL, v-1LL) << "\n";
  31. 			}
  32. 		}
  33. 	}
  34. 	return 0;
  35. }
  36. void Build(long long index, long long start, long long end){
  37. 		lazytree[index] = 0;
  38. 		tree[index] = 0;
  39. 		if(start!=end){
  40. 		Build(index*2 + 1, start, (start + end) >> 1);
  41. 		Build(index*2 + 2, ((start + end) >> 1) + 1, end);
  42. 		}
  43. }
  44. long long Query(long long index, long long start, long long end, long long range_start, long long range_end){
  45. 	if(range_start > end || range_end < start)
  46. 		return 0;
  47. 	else if(range_start <= start && range_end >= end){
  48. 		 return tree[index] + (end - start + 1LL)*(lazytree[index]);
  49. 	}
  50. 	else{
  51. 		MarkChild(index, start, end);
  52. 		return Query(index*2 + 1, start, (start + end) >> 1, range_start, range_end) + Query(index*2 + 2, ((start + end) >> 1) + 1, end, range_start, range_end);
  53. 	}
  54. }
  55. void MarkChild(long long index, long long start, long long end){
  56. 	lazytree[index*2 + 1] += lazytree[index];
  57. 	lazytree[index*2 + 2] += lazytree[index];
  58. 	tree[index] += (end - start + 1LL)*lazytree[index];
  59. 	lazytree[index] = 0;
  60. }
  61. long long update(long long index, long long start, long long end, long long range_start, long long range_end, long long value){
  62. 	if(range_start > end || range_end < start)
  63. 		return 0;
  64. 	else if(range_start <= start && range_end >= end){
  65. 		lazytree[index] += value;
  66. 		return (end - start + 1LL)*value;
  67. 	}
  68. 	else{
  69. 		long long vc = update(index*2 + 1, start, (start + end) >> 1, range_start, range_end, value) + update(index*2 + 2, ((start + end) >> 1) + 1, end, range_start, range_end, value);
  70. 		tree[index] += vc;
  71. 		return vc;
  72. 	}
  73. }
Success #stdin #stdout 0s 11248KB
comments (?)
stdin
copy 
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8
stdout
copy 
80
508
https://ideone.com/JWh9Qx
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!