fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long int
  4. const int N = 2e5+10;
  5.  
  6. int arr[N];
  7. int segTree[4*N+1];
  8.  
  9. void buildSegTree(int idx, int low, int high){
  10. 	if(low == high){
  11. 		segTree[idx] = arr[low];
  12. 		return;
  13. 	}
  14. 	int mid = (low + high) >> 1;
  15. 	buildSegTree(2*idx, low, mid);
  16. 	buildSegTree(2*idx+1, mid+1, high);
  17. 	segTree[idx] = min(segTree[2*idx],segTree[2*idx+1]);
  18. }
  19.  
  20. void updateSegTreePoint(int idx, int low, int high, int index, int val){
  21. 	if(index<low or index>high){
  22. 		return;
  23. 	}
  24. 	if(low == high){
  25. 		segTree[idx] = val;
  26. 		return;
  27. 	}
  28.  
  29. 	int mid = (low+high)>>1;
  30.  
  31. 	if(index <= mid){
  32. 		updateSegTreePoint(2*idx, low, mid, index, val);
  33. 	} else {
  34. 		updateSegTreePoint(2*idx+1, mid+1, high, index, val);
  35. 	}
  36. 	segTree[idx] = min(segTree[2*idx],segTree[2*idx+1]);
  37. }
  38.  
  39. int querySegTree(int idx, int low, int high, int qs, int qe){
  40. 	if(qs <= low and high <= qe){
  41. 		return segTree[idx];
  42. 	}
  43.  
  44. 	if(qe<low or qs>high or low>high){
  45. 		return INT_MAX;
  46. 	}
  47. 	int mid = (low+high)>>1;
  48. 	int left = querySegTree(2*idx, low, mid, qs, qe);
  49. 	int right = querySegTree(2*idx+1, mid+1, high, qs, qe);
  50. 	return min(left,right);
  51. }
  52.  
  53. int32_t main() {
  54. 	int n, q;
  55. 	cin >> n >> q;
  56. 	for(int i=0; i<n; i++){
  57. 		cin>>arr[i];
  58. 	}
  59. 	buildSegTree(1, 0, n-1);
  60. 	while(q--){
  61. 		int t, a, b;
  62. 		cin >> t >> a >> b;
  63. 		if(t==1){
  64. 			updateSegTreePoint(1, 0, n-1, a-1, b);
  65. 		} else {
  66. 			cout << querySegTree(1, 0, n-1, a-1, b-1) << endl;
  67. 		}
  68. 	}
  69. 	return 0;
  70. }
Success #stdin #stdout 0.01s 5568KB
comments (?)
stdin
copy 
8 4
3 2 4 5 1 1 5 3
2 1 4
2 5 6
1 2 3
2 1 4
stdout
copy 
2
1
3
https://ideone.com/ngvDJC
Dynamic Range Minimum Queries
language:
C++14 (gcc 8.3)
created:
5 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!