fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty