#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
vi tempans;
struct segTree {
struct node {
int val=0,mn=1e9,mx=-1e9;
node(int _val=0, int _mn=1e9, int _mx=-1e9): val(_val),mn(_mn),mx(_mx) {}
};
vector<node> nodes;
int sze;
void push(int v, int tl, int tr) {
if (tl!=tr) {
nodes[2*v].mn=min(nodes[v].mn,max(nodes[v].mx,nodes[2*v].mn));
nodes[2*v].mx=min(nodes[v].mn,max(nodes[v].mx,nodes[2*v].mx));
nodes[2*v+1].mn=min(nodes[v].mn,max(nodes[v].mx,nodes[2*v+1].mn));
nodes[2*v+1].mx=min(nodes[v].mn,max(nodes[v].mx,nodes[2*v+1].mx));
}
else {
nodes[v].val=min(nodes[v].mn,max(nodes[v].mx,nodes[v].val));
}
nodes[v].mn=1e9;
nodes[v].mx=-1e9;
}
segTree(int n): sze(n) {
nodes.resize(4*sze);
}
void update(int v, int l, int r, int val, bool mx, int tl, int tr) {
push(v,tl,tr);
if (l<=tl && tr<=r) {
if (mx) {
nodes[v].mx=max(nodes[v].mx,val);
nodes[v].mn=max(nodes[v].mn,val);
}
else {
nodes[v].mx=min(nodes[v].mx,val);
nodes[v].mn=min(nodes[v].mn,val);
}
push(v,tl,tr);
return;
}
if (r<tl || tr<l) {
return;
}
int tm=tl+(tr-tl)/2;
update(2*v,l,r,val,mx,tl,tm);
update(2*v+1,l,r,val,mx,tm+1,tr);
}
void update(int l, int r, int val, bool mx) {
update(1,l,r,val,mx,0,sze-1);
}
void travel(int v, int tl, int tr) {
push(v,tl,tr);
if (tl==tr) {
tempans[tl]=nodes[v].val;
return;
}
int tm=tl+(tr-tl)/2;
travel(2*v,tl,tm);
travel(2*v+1,tm+1,tr);
}
void travel() {
travel(1,0,sze-1);
}
};
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]) {
tempans.resize(n);
segTree data(n);
for (int i=0; i<k; i++) {
data.update(l[i],r[i],h[i],op[i]==1);
}
data.travel();
for (int i=0; i<n; i++) {
ans[i]=tempans[i];
}
}
