#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const int maxn=2e6+5;
const int INF=1e9+5;
const ll mod=1e9+7;
#define ok ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define lb lower_bound
#define ub upper_bpund
#define fi first
#define se second
#define endl '\n'
struct Node {
int max1, max2, min1, min2, lazy;
} seg[maxn*4];
int arr[maxn];
vi ans;
void merge(int now) {
if(seg[now*2].max1==seg[now*2+1].max1) {
seg[now].max1=seg[now*2].max1;
seg[now].max2=max(seg[now*2].max2, seg[now*2+1].max2);
} else {
if(seg[now*2].max1>seg[now*2+1].max1) {
seg[now].max1=seg[now*2].max1;
seg[now].max2=max(seg[now*2].max2, seg[now*2+1].max1);
} else {
seg[now].max1=seg[now*2+1].max1;
seg[now].max2=max(seg[now*2].max1, seg[now*2+1].max2);
}
}
if(seg[now*2].min1==seg[now*2+1].min1) {
seg[now].min1=seg[now*2].min1;
seg[now].min2=min(seg[now*2].min2, seg[now*2+1].min2);
} else {
if(seg[now*2].min1<seg[now*2+1].min1) {
seg[now].min1=seg[now*2].min1;
seg[now].min2=min(seg[now*2].min2, seg[now*2+1].min1);
} else {
seg[now].min1=seg[now*2+1].min1;
seg[now].min2=max(seg[now*2].min1, seg[now*2+1].min2);
}
}
}
// chmin update
void push_max(int now, int l, int r, int val) {
if(val>=seg[now].max1) return;
seg[now].max1=val;
if(l==r) {
seg[now].min1=seg[now].max1;
} else {
if(val<=seg[now].min1) {
seg[now].min1=val;
} else if(val<seg[now].min2) {
seg[now].min2=val;
}
}
}
// chmax update
void push_min(int now, int l, int r, int val) {
if(val<=seg[now].min1) return;
seg[now].min1=val;
if(l==r) {
seg[now].max1=seg[now].min1;
} else {
if(val>=seg[now].max1) {
seg[now].max1=val;
} else if(val>seg[now].max2) {
seg[now].max2=val;
}
}
}
void pushdown(int now, int l, int r) {
if(l==r) return;
int mid=(l+r)/2;
push_max(now*2, l, mid, seg[now].max1);
push_max(now*2+1, mid+1, r, seg[now].max1);
push_min(now*2, l, mid, seg[now].min1);
push_min(now*2+1, mid+1, r, seg[now].min1);
}
void build(int now, int l, int r) {
if(l==r) {
seg[now].max1=seg[now].min1=arr[l];
seg[now].max2=-INF;
seg[now].min2=INF;
} else {
int mid=(l+r)/2;
build(now*2, l, mid);
build(now*2+1, mid+1, r);
merge(now);
}
}
void update_chmin(int now, int l, int r, int posl, int posr, int val) {
if(l>posr || r<posl || val>=seg[now].max1) return;
if(l>=posl && r<=posr && val>seg[now].max2) {
push_max(now, l, r, val);
return;
}
pushdown(now, l, r);
int mid=(l+r)/2;
update_chmin(now*2, l, mid, posl, posr, val);
update_chmin(now*2+1, mid+1, r, posl, posr, val);
merge(now);
}
void update_chmax(int now, int l, int r, int posl, int posr, int val) {
if(l>posr || r<posl || val<=seg[now].min1) return;
if(l>=posl && r<=posr && val<seg[now].min2) {
push_min(now, l, r, val);
return;
}
pushdown(now, l, r);
int mid=(l+r)/2;
update_chmax(now*2, l, mid, posl, posr, val);
update_chmax(now*2+1, mid+1, r, posl, posr, val);
merge(now);
}
void query(int now, int l, int r) {
if(l==r) {
ans.pb(seg[now].max1);
return;
}
pushdown(now, l, r);
int mid=(l+r)/2;
query(now*2, l, mid);
query(now*2+1, mid+1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
build(1, 1, n);
for(int i=0; i<k; i++) {
if(op[i]==1) {
update_chmax(1, 1, n, left[i]+1, right[i]+1, height[i]);
} else if(op[i]==2) {
update_chmin(1, 1, n, left[i]+1, right[i]+1, height[i]);
}
}
query(1, 1, n);
for(int i=0; i<n; i++) finalHeight[i]=ans[i];
}
