fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define LSB(x) ((x) & -(x))
  5.  
  6. template <class T>
  7. struct BIT {
  8. using F = function<T(const T&, const T&)>;
  9.  
  10. const vector<T>& a;
  11. const T nil;
  12. const F f;
  13. const int n;
  14. vector<T> b1, b2;
  15.  
  16. void chf(T& lhs, const T& rhs) {
  17. lhs = f(lhs, rhs);
  18. }
  19.  
  20. BIT(const vector<T>& a_, const T& nil_, const F& f_) : a(a_), nil(nil_), f(f_), n(int(a.size()) - 1), b1(n + 1, nil), b2(n + 1, nil) {
  21. for (int i = 1; i <= n; ++i) {
  22. b1[i] = b2[i] = a[i];
  23. }
  24. for (int i = 1; i <= n; ++i) {
  25. if (i + LSB(i) <= n) {
  26. chf(b1[i + LSB(i)], b1[i]);
  27. }
  28. }
  29. for (int i = n; i >= 1; --i) {
  30. if (i - LSB(i) >= 1) {
  31. chf(b2[i - LSB(i)], b2[i]);
  32. }
  33. }
  34. }
  35.  
  36. T query(int L, int R) {
  37. if (L > R) return nil;
  38. T res = nil;
  39. int i;
  40. for (i = L; i + LSB(i) <= R; i += LSB(i)) {
  41. chf(res, b2[i]);
  42. }
  43. for (i = R; i - LSB(i) >= L; i -= LSB(i)) {
  44. chf(res, b1[i]);
  45. }
  46. return f(res, a[i]);
  47. }
  48.  
  49. void update(int p, const T& v) {
  50. b1[p] = b2[p] = v;
  51. for (int i = p - 1; i >= 1 && i > p - LSB(p); i -= LSB(i)) {
  52. chf(b1[p], b1[i]);
  53. }
  54. for (int i = p + 1; i <= n && p <= i - LSB(i); i += LSB(i)) {
  55. chf(b2[p], b2[i]);
  56. }
  57. T cur = nil;
  58. for (int i = p, j = p - 1; i <= n; i += LSB(i)) {
  59. for (; j >= 1 && j > i - LSB(i); j -= LSB(j)) {
  60. chf(cur, b1[j]);
  61. }
  62. b1[i] = f(cur, a[i]);
  63. chf(cur, b2[i]);
  64. }
  65. cur = nil;
  66. for (int i = p, j = p + 1; i >= 1; i -= LSB(i)) {
  67. for (; j <= n && i <= j - LSB(j); j += LSB(j)) {
  68. chf(cur, b2[j]);
  69. }
  70. b2[i] = f(cur, a[i]);
  71. chf(cur, b1[i]);
  72. }
  73. }
  74. };
  75.  
  76. int main() {
  77. ios::sync_with_stdio(false);
  78. cin.tie(nullptr);
  79. int n, q;
  80. cin >> n >> q;
  81. vector<int> x(n + 1);
  82. for (int i = 1; i <= n; ++i) {
  83. cin >> x[i];
  84. }
  85. BIT<int> bit(x, INT_MAX, [&](int lhs, int rhs) { return min(lhs, rhs); });
  86. while (q--) {
  87. int op;
  88. cin >> op;
  89. if (op == 1) {
  90. int k, u;
  91. cin >> k >> u;
  92. ++k;
  93. x[k] = u;
  94. bit.update(k, u);
  95. } else {
  96. int a, b;
  97. cin >> a >> b;
  98. ++a; ++b;
  99. cout << bit.query(a, b - 1) << "\n";
  100. }
  101. }
  102. return 0;
  103. }
Success #stdin #stdout 0.01s 5636KB
stdin
5 5
5 4 2 3 5
2 0 3
1 2 6
2 0 3
1 3 1
2 0 5
stdout
2
4
1