#include<bits/stdc++.h>
#include"wall.h"
using namespace std;
typedef long long ll;
struct segtree{
struct node{
int opt, num;
node() : opt(-1), num(0){}
};
vector<node> tree;
int N;
segtree(const int& treesize) : N(treesize){
tree.resize(4*N+5);
tree[1].opt = 2, tree[1].num = 0;
}
void push(int v, bool side){
if(tree[v].opt == -1)
return;
int where = (side ? v*2+1 : v*2);
if(tree[where].opt == -1){
tree[where] = tree[v];
} else if(tree[v].opt == tree[where].opt){
if(tree[v].opt == 1){
tree[where].num = max(tree[where].num, tree[v].num);
} else{
tree[where].num = min(tree[where].num, tree[v].num);
}
} else if(tree[v].opt == 1 && tree[where].opt == 2){
if(tree[v].num >= tree[where].num){
tree[where].opt = 1;
tree[where].num = tree[v].num;
}
} else if(tree[v].opt == 2 && tree[where].opt == 1){
if(tree[v].num <= tree[where].num){
tree[where].opt = 2;
tree[where].num = tree[v].num;
}
}
if(side == 1)
tree[v].opt = -1;
}
void max_update(int v, int l, int r, int L, int R, int D){
if(l > R || r < L){
return;
}
if(r <= R && l >= L){
if(tree[v].opt == -1 || tree[v].num <= D){
tree[v].num = D;
tree[v].opt = 1;
}
return;
}
push(v, 0), push(v, 1);
int mid = (l+r)/2;
max_update(v*2, l, mid, L, R, D);
max_update(v*2+1, mid+1, r, L, R, D);
}
void min_update(int v, int l, int r, int L, int R, int D){
if(l > R || r < L){
return;
}
if(r <= R && l >= L){
if(tree[v].opt == -1 || tree[v].num >= D){
tree[v].num = D;
tree[v].opt = 2;
}
return;
}
push(v, 0), push(v, 1);
int mid = (l+r)/2;
min_update(v*2, l, mid, L, R, D);
min_update(v*2+1, mid+1, r, L, R, D);
}
void max_update(int L, int R, int D){
max_update(1, 0, N, L, R, D);
}
void min_update(int L, int R, int D){
min_update(1, 0, N, L, R, D);
}
int get(int v, int l, int r, int I){
if(l == r)
return tree[v].num;
push(v, 0), push(v, 1);
int mid = (l+r)/2;
if(I <= mid)
return get(v*2, l, mid, I);
else
return get(v*2+1, mid+1, r, I);
}
int operator[](int I){
return get(1, 0, N, I);
}
void dfs(int v, int l, int r){
cout << l << " " << r << ": ";
cout << tree[v].num << " " << tree[v].opt << "\n";
if(l == r){
return;
}
push(v, 0);
push(v, 1);
int mid = (l+r)/2;
dfs(v*2, l, mid), dfs(v*2+1, mid+1, r);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
segtree ST(n);
for(int i = 0; i < k; i++){
if(op[i] == 1){
ST.max_update(left[i], right[i], height[i]);
} else{
ST.min_update(left[i], right[i], height[i]);
}
}
for(int i = 0; i < n; i++)
finalHeight[i] = ST[i];
}
/*
void solve(){
int n, k;
cin >> n >> k;
int op[k], left[k], right[k], height[n];
// maximize = 1, minimize = 2
for(int i = 0; i < k; i++)
cin >> op[i] >> left[i] >> right[i] >> height[i];
int finalHeight[n] = {};
buildWall(n, k, op, left, right, height, finalHeight);
for(int i = 0; i < n; i++)
cout << finalHeight[i] << " ";
cout << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int tt = 1;
// cin >> tt;
while(tt--){
solve();
}
}*/
