fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. void build_segment_tree(int *arr, int *a, int node, int start, int end)
  4. {
  5. 	if(start == end)
  6. 	{
  7. 		arr[node] = a[start];
  8. 		return;
  9. 	}
  10. 	int mid = (start+end) / 2;
  11. 	build_segment_tree(arr, a, 2*node+1, start, mid);
  12. 	build_segment_tree(arr, a, 2*node+2, mid+1, end);
  13. 	arr[node] = min(arr[2*node+1], arr[2*node+2]);
  14. }
  15.  
  16. void update_segment_tree(int *arr, int *a, int node, int start, int end, int idx, int new_value)
  17. {
  18. 	if(start == end)
  19. 	{
  20. 		a[idx] = new_value;
  21. 		arr[node] = new_value;
  22. 		return;
  23. 	}	
  24. 	int mid = (start+end)/2;
  25. 	if(start <= idx && idx <= end)
  26. 	{
  27. 		update_segment_tree(arr, a, 2*node+1, start, mid, idx, new_value);
  28. 	}
  29. 	else
  30. 	{
  31. 		update_segment_tree(arr, a, 2*node+2, mid+1, end, idx, new_value);
  32. 	}
  33. 	arr[node] = min(arr[2*node+1], arr[2*node+2]);
  34. }
  35.  
  36. int query(int *arr, int *a, int node, int start, int end, int l, int r)
  37. {
  38. 	if(r < start || end < l)
  39. 		return INT_MAX;
  40. 	if(l <= start && end <= r)
  41. 	{
  42. 		return arr[node];
  43. 	}
  44. 	int mid = (start+end)/2;
  45. 	int p1 = query(arr, a, 2*node+1, start, mid, l, r);
  46. 	int p2 = query(arr, a, 2*node+2, mid+1, end, l, r);
  47. 	return min(p1, p2);
  48. }
  49.  
  50. int main()
  51. {
  52. 	int n, q;
  53. 	cin >> n >> q;
  54. 	int a[n];
  55. 	for(int i = 0; i < n; i++)
  56. 	{
  57. 		cin >> a[i];
  58. 	}
  59. 	int arr[3*n];
  60. 	memset(arr, INT_MAX, sizeof(a));
  61. 	build_segment_tree(arr, a, 0, 0, n-1);
  62. 	char temp;
  63. 	int l, r;
  64. 	while(q--)
  65. 	{
  66. 		cin >> temp >> l >> r;
  67. 		if(temp == 'q')
  68. 		{
  69. 			l--, r--;
  70. 			cout << query(arr, a, 0, 0, n-1, l, r) << '\n';
  71. 		}
  72. 		else
  73. 		{
  74. 			l--;
  75. 			update_segment_tree(arr, a, 0, 0, n-1, l, r);
  76. 		}
  77. 	}
  78. 	return 0;
  79. }
Success #stdin #stdout 0.01s 5452KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YbUKar
language:
C++14 (gcc 8.3)
created:
2 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!