fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int inf  = 1e9 + 7;
  6. const int maxN = 1e5 + 7;
  7.  
  8. int n, m;
  9. int a[maxN];
  10. int leaf[4 * maxN]; // Lưu chỉ số của nút lá tương ứng với phần tử ở vị trí i trong dãy số
  11. multiset <int> st[4 * maxN];
  12.  
  13. void build(int id, int l, int r) {
  14.     if (l == r) {
  15.         leaf[l] = id;
  16.         st[id].insert(a[l]);
  17.         return;
  18.     }
  19.     int mid = l + r >> 1;
  20.     build(2 * id, l, mid);
  21.     build(2 * id + 1, mid + 1, r);
  22.  
  23.     st[id] = st[2 * id + 1];
  24.     for (auto x : st[2 * id]) st[id].insert(x);
  25. }
  26.  
  27. void update(int i, int val){
  28.     int id  = leaf[i]; 
  29.     int old = *st[id].begin();
  30.     while (id) {
  31.         st[id].erase(st[id].find(old));
  32.         st[id].insert(val);
  33.         id /= 2;
  34.     }
  35. }
  36.  
  37. int get(int id, int l, int r, int u, int v, int k) {
  38.     if (l >  v || r <  u) return inf; 
  39.     if (l >= u && r <= v) {
  40.         auto it = st[id].lower_bound(k);
  41.         if (it == st[id].end()) return inf;
  42.         return *it;
  43.     }
  44.  
  45.     int mid = l + r >> 1;
  46.     int get1 = get(2 * id, l, mid, u, v, k);
  47.     int get2 = get(2 * id + 1, mid + 1, r, u, v, k);
  48.     return min(get1, get2);
  49. }
  50.  
  51. int main() {
  52.     cin >> n >> m;
  53.     for (int i = 1; i <= n; ++i) cin >> a[i];
  54.     build(1, 1, n);
  55.  
  56.     while (m--){
  57.         int type, l, r, k;
  58.         cin >> type;
  59.         if (type == 1) {
  60.             cin >> l >> k;
  61.             update(l, k);
  62.         }
  63.         else {
  64.             cin >> l >> r >> k;
  65.             int ans = get(1, 1, n, l, r, k);
  66.             cout << ((ans == inf) ? -1 : ans) << '\n';
  67.         }
  68.     }
  69. }
  70.  
Success #stdin #stdout 0.01s 23896KB
comments (?)
stdin
copy 
5 4
1 5 3 4 5
2 1 3 2
2 3 5 6
1 2 2
2 1 5 2
stdout
copy 
3
-1
2
https://ideone.com/NQjQEa
language:
C++14 (gcc 8.3)
created:
2 years 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!