fork download
copy 
  1. #include <bits/stdc++.h>
  2. // #include <boost/multiprecision/cpp_int.hpp>
  3.  
  4. // using namespace boost::multiprecision;
  5.  
  6. // #define int cpp_int
  7. #define int long long
  8. #define ull unsigned long long
  9. #define EPS 1e-9
  10.  
  11. #define test_case \
  12.   int t;          \
  13.   cin >> t;       \
  14.   while (t--)
  15.  
  16. #define print_case cout << "Case " << ++cas << ": "
  17. #define mod (int) 1e9+7
  18. const int N = 1e5+7;
  19. const int INF = INT64_MAX;
  20. using namespace std;
  21. int a[4*N], sol[4*N];
  22. void make_seg_tree(int node, int b, int e) {
  23.     if(b==e) {
  24.       a[node] = sol[b]; return;
  25.     } 
  26.     int mid = (b + e) >> 1, left = node * 2, right = (node * 2) + 1;
  27.     make_seg_tree(left, b, mid);
  28.     make_seg_tree(right, mid+1, e);
  29.     a[node] = min(a[left], a[right]);
  30. }
  31. void upd(int node, int b, int e, int ind, int value) {
  32.   if(ind > e or ind < b) return;
  33.   if(b == e and b == ind) {
  34.     a [node] = value;
  35.     return;
  36.   }
  37.   int l = node * 2, r =2 * node  + 1;
  38.   int mid = (b + e) >> 1;
  39.   upd(l, b, mid, ind, value);
  40.   upd(r, mid+1, e, ind, value);
  41.   a[node] = min(a[l], a[r]);
  42. }
  43. int gen_output(int node, int b, int e, int i, int j) {
  44.   if(i>e or j<b) return INF;
  45.   if(b>=i and e<=j) return a[node];
  46.   int left = node * 2, right = (node * 2) + 1;
  47.   int mid = b + e >> 1;
  48.   int l = gen_output(left, b, mid, i, j);
  49.   int r = gen_output (right, mid+1, e, i, j);
  50.   return min(l, r);
  51.  
  52. }
  53. void solve() {
  54.     int n, m; cin >> n >> m;
  55.     for(int i=1; i<=n; i++) cin >> sol[i];
  56.     make_seg_tree(1, 1, n);
  57.     while(m--) {
  58.       int typ; cin >> typ;
  59.       if(typ == 1) {
  60.           int ind, value; cin >> ind >> value;
  61.           upd(1, 1, n, ind+1, value);
  62.       }
  63.       else {
  64.          int i, j; cin >> i >> j;
  65.          cout << gen_output(1, 1, n, i+1, j)<<'\n';
  66.       }
  67.     }
  68. }
  69.  
  70. int32_t main()
  71. {
  72.   ios::sync_with_stdio(false);
  73.   cin.tie(NULL), cout.tie(NULL);
  74. #ifndef ONLINE_JUDGE
  75.       freopen("input.txt", "r", stdin);
  76.   freopen("output.txt", "w", stdout);
  77. #endif
  78.  // test_case
  79.   solve(),
  80.       cout<<'\n';
  81.   return 0;
  82. }
Success #stdin #stdout 0.01s 5488KB
comments (?)
stdin
copy 
5 5
5 4 2 3 5
2 0 3
1 2 6
2 0 3
1 3 1
2 0 5
stdout
copy 
2
4
1
https://ideone.com/KeyxXZ
language:
C++14 (clang 8.0)
created:
1 year ago
visibility:
secret

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!