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.     int n;
  15.     pii tree[sz << 1];
  16.     int lazy[sz << 1];
  17.     bool haveLazy[sz << 1];
  18.     void init(int _n){
  19.     	n = _n;
  20.     	memset(haveLazy, 0, sizeof haveLazy);
  21.         for(int i=0; i<n; i++) tree[i+sz] = pii(-inf, i);
  22.         for(int i=sz-1; i>=1; i--) tree[i] = merge(tree[i*2], tree[i*2+1]);
  23.     }
  24.     void push(int node, int s, int e){
  25.     	if(!haveLazy[node]) return;
  26.     	tree[node] = pii(lazy[node], s);
  27.     	if(s != e){
  28.     		lazy[node*2] = lazy[node];
  29.     		lazy[node*2+1] = lazy[node];
  30.     		haveLazy[node*2] = 1;
  31.     		haveLazy[node*2+1] = 1;
  32.     	}
  33.     	haveLazy[node] = 0;
  34.     }
  35.     void update(int l, int r, int v, int node, int s, int e){
  36.     	push(node, s, e);
  37.     	if(r < s || e < l) return;
  38.     	if(l <= s && e <= r){
  39.     		lazy[node] = v;
  40.     		haveLazy[node] = 1;
  41.     		push(node, s, e);
  42.     		return;
  43.     	}
  44.     	int m = (s + e) / 2;
  45.     	update(l, r, v, node*2, s, m);
  46.     	update(l, r, v, node*2+1, m+1, e);
  47.     	tree[node] = merge(tree[node*2], tree[node*2+1]);
  48.     }
  49.     void update(int l, int r, int v){ update(l, r, v, 1, 0, n-1); }
  50.     pii query(int l, int r, int node, int s, int e){
  51.     	push(node, s, e);
  52.     	if(r < s || e < l) return pii(-inf, inf);
  53.     	if(l <= s && e <= r) return tree[node];
  54.     	int m = (s + e) / 2;
  55.     	pii t1 = query(l, r, node*2, s, m);
  56.     	pii t2 = query(l, r, node*2+1, m+1, e);
  57.     	return merge(t1, t2);
  58.     }
  59.     int query(int l, int r){ return query(l, r, 1, 0, n-1).second; }
  60. };
  61.  
  62. int main(){
  63.     ios_base::sync_with_stdio(false); cin.tie(nullptr);
  64.     int initialArray[4] = {5, 4, 3, 9};
  65.     SegmentTree ST; ST.init(4);
  66.     for(int i=0; i<4; i++) ST.update(i, i, initialArray[i]);
  67.  
  68.     ST.update(1, 2, 4); // first query (2, 3, 4), [5, 4, 4, 9]
  69.     for(int i=0; i<4; i++) cout << ST.query(i, i, 1, 0, 4-1).first << " "; cout << "\n";
  70.     cout << ST.query(0, 3) << "\n"; // second query (0, 3), expected : 3
  71.     ST.update(0, 3, 100); // first query (0, 100), [100, 100, 100, 100]
  72.     for(int i=0; i<4; i++) cout << ST.query(i, i, 1, 0, 4-1).first << " "; cout << "\n";
  73.     cout << ST.query(0, 3) << "\n"; // second query (0, 3), expected : 0
  74.     ST.update(1, 2, 4); // first query (3, 100), [100, 4, 4, 100]
  75.     for(int i=0; i<4; i++) cout << ST.query(i, i, 1, 0, 4-1).first << " "; cout << "\n";
  76.     cout << ST.query(0, 1) << "\n"; // second query (0, 1), expected : 0
  77. }
Success #stdin #stdout 0s 5932KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5 4 4 9 
3
100 100 100 100 
0
100 4 4 100 
0
https://ideone.com/Fa5oy1
language:
C++14 (gcc 8.3)
created:
3 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!