fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct SegmentTree{
  5.     typedef pair<int, int> pii;
  6.     static const int sz = 1 << 17; // sz > MAX_SIZE
  7.     static const int inf = 1e9+7;
  8.     static pii merge(pii a, pii b){
  9.         if(a.first > b.first) return a;
  10.         if(a.first < b.first) return b;
  11.         if(a.second < b.second) return a;
  12.         return b;
  13.     }
  14.     pii tree[sz << 1];
  15.     void init(int n){
  16.         for(int i=0; i<n; i++) tree[i+sz] = pii(-inf, i);
  17.         for(int i=sz-1; i>=1; i--) tree[i] = merge(tree[i*2], tree[i*2+1]);
  18.     }
  19.     void update(int x, int v){
  20.         x += sz; tree[x].first = v;
  21.         while(x /= 2) tree[x] = merge(tree[x*2], tree[x*2+1]);
  22.     }
  23.     int query(int l, int r){
  24.         l += sz; r += sz; pii ret(-inf, inf);
  25.         while(l <= r){
  26.             if(l % 2 == 1) ret = merge(ret, tree[l++]);
  27.             if(r % 2 == 0) ret = merge(ret, tree[r--]);
  28.             l /= 2; r /= 2;
  29.         }
  30.         return ret.second;
  31.     }
  32. };
  33.  
  34. int main(){
  35.     ios_base::sync_with_stdio(false); cin.tie(nullptr);
  36.     int initialArray[4] = {5, 4, 3, 9};
  37.     SegmentTree ST; ST.init(4);
  38.     for(int i=0; i<4; i++) ST.update(i, initialArray[i]);
  39.  
  40.     ST.update(2, 4); // first query (2, 4), [5, 4, 4, 9]
  41.     cout << ST.query(0, 3) << "\n"; // second query (0, 3), expected : 3
  42.     ST.update(0, 100); // first query (0, 100), [100, 4, 4, 9]
  43.     ST.update(3, 100); // first query (3, 100), [100, 4, 4, 100]
  44.     cout << ST.query(0, 1) << "\n"; // second query (0, 1), expected : 0
  45. }
Success #stdin #stdout 0s 5632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
0
https://ideone.com/M1l9vm
language:
C++14 (gcc 8.3)
created:
4 years 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!