fork download
copy 
  1. #include<bits\stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5.  
  6. struct node
  7. {
  8. 	int sum=0;
  9. 	int arr[41] = { 0 };
  10. 	node(int x = 0) {
  11. 		arr[x] = 1;
  12. 		sum = 0;
  13. 	}
  14.  
  15. };
  16. node out()
  17. {
  18. 	return node(0);
  19. }
  20. node proces(node a, node b)
  21. {
  22. 	node c;
  23. 	c.sum = a.sum + b.sum;
  24. 	int sum = 0;;
  25. 	for (int i = 1; i <= 40; i++)
  26. 	{
  27. 		c.arr[i] = a.arr[i] + b.arr[i];
  28. 		c.sum += sum*a.arr[i];
  29. 		sum += b.arr[i];
  30. 	}
  31. 	return c;
  32. }
  33. int const nn = 4e5 + 1;
  34. int n;
  35. int a1[nn];
  36. node tree1[nn];
  37. void build_tree(node *tree, int *a, int s, int e, int ind)
  38. {
  39. 	if (s == e)
  40. 	{
  41. 		tree[ind] = node(a[s]);
  42. 		return;
  43. 	}
  44. 	int mid = (s + e) / 2;
  45. 	build_tree(tree, a, s, mid, ind * 2);
  46. 	build_tree(tree, a, mid + 1, e, (ind * 2) + 1);
  47. 	tree[ind] = proces(tree[ind * 2], tree[(ind * 2) + 1]);
  48. 	return;
  49. }
  50. node query(node *tree, int ss, int se, int qs, int qe, int ind)
  51. {
  52. 	//complete overlap
  53. 	if (ss >= qs && se <= qe)
  54. 		return tree[ind];
  55.  
  56. 	// no overlap
  57. 	if (qe<ss || qs>se)
  58. 		return out();
  59. 	int mid = (ss + se) / 2;
  60. 	node left = query(tree, ss, mid, qs, qe, ind * 2);
  61. 	node right = query(tree, mid + 1, se, qs, qe, ind * 2 + 1);
  62. 	return proces(left, right);
  63.  
  64. }
  65. void update(node *tree, int ss, int se, int i, int new_val, int ind)
  66. {
  67. 	//case where the I is out of bound 
  68. 	if (i > se || i < ss)
  69. 		return;
  70.  
  71. 	// leaf node 
  72. 	if (ss == se)
  73. 	{
  74. 		tree[ind] = node(new_val);
  75. 		return;
  76. 	}
  77. 	//otherwise 
  78. 	int mid = (ss + se) / 2;
  79. 	update(tree, ss, mid, i, new_val, ind * 2);
  80. 	update(tree, mid + 1, se, i, new_val, ind * 2 + 1);
  81.  
  82. 	tree[ind] = proces(tree[ind * 2], tree[ind * 2 + 1]);
  83. 	return;
  84. }
  85.  
  86. int32_t main()
  87. {
  88. 	int n, m;
  89. 	cin >> n >> m;
  90. 	for (int i = 1; i <= n; i++)
  91. 		cin >> a1[i];
  92. 	build_tree(tree1, a1, 1, n, 1);
  93. 	while (m--)
  94. 	{
  95. 		int ty;
  96. 		cin >> ty;
  97. 		if (ty == 1)
  98. 		{
  99. 			int x, y;
  100. 			cin >> x >> y;
  101. 			node num = query(tree1, 1, n, x, y, 1);
  102. 			cout << num.sum << endl;
  103. 		}
  104. 		else {
  105. 			int ind, v;
  106. 			cin >> ind >> v;
  107. 			update(tree1, 1, n, ind, v, 1);
  108. 		}
  109.  
  110. 	}
  111. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:1:9: fatal error: bits\stdc++.h: No such file or directory
 #include<bits\stdc++.h>
         ^~~~~~~~~~~~~~~
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/iyqcQI
language:
C++14 (gcc 8.3)
created:
341 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!