#include <bits/stdc++.h>
using namespace std;
struct SegmentTree{
typedef pair<int, int> pii;
static const int sz = 1 << 17; // sz > MAX_SIZE
static const int inf = 1e9+7;
static pii merge(pii a, pii b){
if(a.first > b.first) return a;
if(a.first < b.first) return b;
if(a.second < b.second) return a;
return b;
}
int n;
pii tree[sz << 1];
int lazy[sz << 1];
bool haveLazy[sz << 1];
void init(int _n){
n = _n;
memset(haveLazy, 0, sizeof haveLazy);
for(int i=0; i<n; i++) tree[i+sz] = pii(-inf, i);
for(int i=sz-1; i>=1; i--) tree[i] = merge(tree[i*2], tree[i*2+1]);
}
void push(int node, int s, int e){
if(!haveLazy[node]) return;
tree[node] = pii(lazy[node], s);
if(s != e){
lazy[node*2] = lazy[node];
lazy[node*2+1] = lazy[node];
haveLazy[node*2] = 1;
haveLazy[node*2+1] = 1;
}
haveLazy[node] = 0;
}
void update(int l, int r, int v, int node, int s, int e){
push(node, s, e);
if(r < s || e < l) return;
if(l <= s && e <= r){
lazy[node] = v;
haveLazy[node] = 1;
push(node, s, e);
return;
}
int m = (s + e) / 2;
update(l, r, v, node*2, s, m);
update(l, r, v, node*2+1, m+1, e);
tree[node] = merge(tree[node*2], tree[node*2+1]);
}
void update(int l, int r, int v){ update(l, r, v, 1, 0, n-1); }
pii query(int l, int r, int node, int s, int e){
push(node, s, e);
if(r < s || e < l) return pii(-inf, inf);
if(l <= s && e <= r) return tree[node];
int m = (s + e) / 2;
pii t1 = query(l, r, node*2, s, m);
pii t2 = query(l, r, node*2+1, m+1, e);
return merge(t1, t2);
}
int query(int l, int r){ return query(l, r, 1, 0, n-1).second; }
};
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int initialArray[4] = {5, 4, 3, 9};
SegmentTree ST; ST.init(4);
for(int i=0; i<4; i++) ST.update(i, i, initialArray[i]);
ST.update(1, 2, 4); // first query (2, 3, 4), [5, 4, 4, 9]
for(int i=0; i<4; i++) cout << ST.query(i, i, 1, 0, 4-1).first << " "; cout << "\n";
cout << ST.query(0, 3) << "\n"; // second query (0, 3), expected : 3
ST.update(0, 3, 100); // first query (0, 100), [100, 100, 100, 100]
for(int i=0; i<4; i++) cout << ST.query(i, i, 1, 0, 4-1).first << " "; cout << "\n";
cout << ST.query(0, 3) << "\n"; // second query (0, 3), expected : 0
ST.update(1, 2, 4); // first query (3, 100), [100, 4, 4, 100]
for(int i=0; i<4; i++) cout << ST.query(i, i, 1, 0, 4-1).first << " "; cout << "\n";
cout << ST.query(0, 1) << "\n"; // second query (0, 1), expected : 0
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3QgU2VnbWVudFRyZWV7Cgl0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IHBpaTsKICAgIHN0YXRpYyBjb25zdCBpbnQgc3ogPSAxIDw8IDE3OyAvLyBzeiA+IE1BWF9TSVpFCiAgICBzdGF0aWMgY29uc3QgaW50IGluZiA9IDFlOSs3OwogICAgc3RhdGljIHBpaSBtZXJnZShwaWkgYSwgcGlpIGIpewogICAgICAgIGlmKGEuZmlyc3QgPiBiLmZpcnN0KSByZXR1cm4gYTsKICAgICAgICBpZihhLmZpcnN0IDwgYi5maXJzdCkgcmV0dXJuIGI7CiAgICAgICAgaWYoYS5zZWNvbmQgPCBiLnNlY29uZCkgcmV0dXJuIGE7CiAgICAgICAgcmV0dXJuIGI7CiAgICB9CiAgICBpbnQgbjsKICAgIHBpaSB0cmVlW3N6IDw8IDFdOwogICAgaW50IGxhenlbc3ogPDwgMV07CiAgICBib29sIGhhdmVMYXp5W3N6IDw8IDFdOwogICAgdm9pZCBpbml0KGludCBfbil7CiAgICAJbiA9IF9uOwogICAgCW1lbXNldChoYXZlTGF6eSwgMCwgc2l6ZW9mIGhhdmVMYXp5KTsKICAgICAgICBmb3IoaW50IGk9MDsgaTxuOyBpKyspIHRyZWVbaStzel0gPSBwaWkoLWluZiwgaSk7CiAgICAgICAgZm9yKGludCBpPXN6LTE7IGk+PTE7IGktLSkgdHJlZVtpXSA9IG1lcmdlKHRyZWVbaSoyXSwgdHJlZVtpKjIrMV0pOwogICAgfQogICAgdm9pZCBwdXNoKGludCBub2RlLCBpbnQgcywgaW50IGUpewogICAgCWlmKCFoYXZlTGF6eVtub2RlXSkgcmV0dXJuOwogICAgCXRyZWVbbm9kZV0gPSBwaWkobGF6eVtub2RlXSwgcyk7CiAgICAJaWYocyAhPSBlKXsKICAgIAkJbGF6eVtub2RlKjJdID0gbGF6eVtub2RlXTsKICAgIAkJbGF6eVtub2RlKjIrMV0gPSBsYXp5W25vZGVdOwogICAgCQloYXZlTGF6eVtub2RlKjJdID0gMTsKICAgIAkJaGF2ZUxhenlbbm9kZSoyKzFdID0gMTsKICAgIAl9CiAgICAJaGF2ZUxhenlbbm9kZV0gPSAwOwogICAgfQogICAgdm9pZCB1cGRhdGUoaW50IGwsIGludCByLCBpbnQgdiwgaW50IG5vZGUsIGludCBzLCBpbnQgZSl7CiAgICAJcHVzaChub2RlLCBzLCBlKTsKICAgIAlpZihyIDwgcyB8fCBlIDwgbCkgcmV0dXJuOwogICAgCWlmKGwgPD0gcyAmJiBlIDw9IHIpewogICAgCQlsYXp5W25vZGVdID0gdjsKICAgIAkJaGF2ZUxhenlbbm9kZV0gPSAxOwogICAgCQlwdXNoKG5vZGUsIHMsIGUpOwogICAgCQlyZXR1cm47CiAgICAJfQogICAgCWludCBtID0gKHMgKyBlKSAvIDI7CiAgICAJdXBkYXRlKGwsIHIsIHYsIG5vZGUqMiwgcywgbSk7CiAgICAJdXBkYXRlKGwsIHIsIHYsIG5vZGUqMisxLCBtKzEsIGUpOwogICAgCXRyZWVbbm9kZV0gPSBtZXJnZSh0cmVlW25vZGUqMl0sIHRyZWVbbm9kZSoyKzFdKTsKICAgIH0KICAgIHZvaWQgdXBkYXRlKGludCBsLCBpbnQgciwgaW50IHYpeyB1cGRhdGUobCwgciwgdiwgMSwgMCwgbi0xKTsgfQogICAgcGlpIHF1ZXJ5KGludCBsLCBpbnQgciwgaW50IG5vZGUsIGludCBzLCBpbnQgZSl7CiAgICAJcHVzaChub2RlLCBzLCBlKTsKICAgIAlpZihyIDwgcyB8fCBlIDwgbCkgcmV0dXJuIHBpaSgtaW5mLCBpbmYpOwogICAgCWlmKGwgPD0gcyAmJiBlIDw9IHIpIHJldHVybiB0cmVlW25vZGVdOwogICAgCWludCBtID0gKHMgKyBlKSAvIDI7CiAgICAJcGlpIHQxID0gcXVlcnkobCwgciwgbm9kZSoyLCBzLCBtKTsKICAgIAlwaWkgdDIgPSBxdWVyeShsLCByLCBub2RlKjIrMSwgbSsxLCBlKTsKICAgIAlyZXR1cm4gbWVyZ2UodDEsIHQyKTsKICAgIH0KICAgIGludCBxdWVyeShpbnQgbCwgaW50IHIpeyByZXR1cm4gcXVlcnkobCwgciwgMSwgMCwgbi0xKS5zZWNvbmQ7IH0KfTsKIAppbnQgbWFpbigpewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IGNpbi50aWUobnVsbHB0cik7CiAgICBpbnQgaW5pdGlhbEFycmF5WzRdID0gezUsIDQsIDMsIDl9OwogICAgU2VnbWVudFRyZWUgU1Q7IFNULmluaXQoNCk7CiAgICBmb3IoaW50IGk9MDsgaTw0OyBpKyspIFNULnVwZGF0ZShpLCBpLCBpbml0aWFsQXJyYXlbaV0pOwogCiAgICBTVC51cGRhdGUoMSwgMiwgNCk7IC8vIGZpcnN0IHF1ZXJ5ICgyLCAzLCA0KSwgWzUsIDQsIDQsIDldCiAgICBmb3IoaW50IGk9MDsgaTw0OyBpKyspIGNvdXQgPDwgU1QucXVlcnkoaSwgaSwgMSwgMCwgNC0xKS5maXJzdCA8PCAiICI7IGNvdXQgPDwgIlxuIjsKICAgIGNvdXQgPDwgU1QucXVlcnkoMCwgMykgPDwgIlxuIjsgLy8gc2Vjb25kIHF1ZXJ5ICgwLCAzKSwgZXhwZWN0ZWQgOiAzCiAgICBTVC51cGRhdGUoMCwgMywgMTAwKTsgLy8gZmlyc3QgcXVlcnkgKDAsIDEwMCksIFsxMDAsIDEwMCwgMTAwLCAxMDBdCiAgICBmb3IoaW50IGk9MDsgaTw0OyBpKyspIGNvdXQgPDwgU1QucXVlcnkoaSwgaSwgMSwgMCwgNC0xKS5maXJzdCA8PCAiICI7IGNvdXQgPDwgIlxuIjsKICAgIGNvdXQgPDwgU1QucXVlcnkoMCwgMykgPDwgIlxuIjsgLy8gc2Vjb25kIHF1ZXJ5ICgwLCAzKSwgZXhwZWN0ZWQgOiAwCiAgICBTVC51cGRhdGUoMSwgMiwgNCk7IC8vIGZpcnN0IHF1ZXJ5ICgzLCAxMDApLCBbMTAwLCA0LCA0LCAxMDBdCiAgICBmb3IoaW50IGk9MDsgaTw0OyBpKyspIGNvdXQgPDwgU1QucXVlcnkoaSwgaSwgMSwgMCwgNC0xKS5maXJzdCA8PCAiICI7IGNvdXQgPDwgIlxuIjsKICAgIGNvdXQgPDwgU1QucXVlcnkoMCwgMSkgPDwgIlxuIjsgLy8gc2Vjb25kIHF1ZXJ5ICgwLCAxKSwgZXhwZWN0ZWQgOiAwCn0=