#include "wall.h"
# include <bits/stdc++.h>
using namespace std;
const int MXN = 2e6;
int bl[4 * MXN + 1], br[4 * MXN + 1];
void build(int lf, int rg, int nd) {
bl[nd] = br[nd] = 0;
if(lf != rg) {
int mid = (lf + rg) / 2;
build(lf, mid, 2*nd+1);
build(mid+1, rg, 2*nd+2);
}
}
void upd_lazy(int lf, int rg, int nd) {
if(lf != rg) {
int mid = (lf + rg) / 2;
if(bl[2*nd+1] > bl[nd]) bl[2*nd+1] = bl[nd];
else if(bl[2*nd+1] < br[nd]) bl[2*nd+1] = br[nd];
if(bl[2*nd+2] > bl[nd]) bl[2*nd+2] = bl[nd];
else if(bl[2*nd+2] < br[nd]) bl[2*nd+2] = br[nd];
if(br[2*nd+1] > bl[nd]) br[2*nd+1] = bl[nd];
else if(br[2*nd+1] < br[nd]) br[2*nd+1] = br[nd];
if(br[2*nd+2] > bl[nd]) br[2*nd+2] = bl[nd];
else if(br[2*nd+2] < br[nd]) br[2*nd+2] = br[nd];
}
}
void upd(int lf, int rg, int nd, int clf, int crg, int op, int pos) {
upd_lazy(lf, rg, nd);
if(clf > rg || lf > crg) return;
else if(clf <= lf && rg <= crg) {
if(op == 1) {
// cout<<"upd : "<<lf<<" "<<rg<<" "<<nd<<" "<<bl[nd]<<" "<<pos<<endl;
if(bl[nd] <= pos) bl[nd] = br[nd] = pos;
else if(br[nd] <= pos) br[nd] = pos;
} else {
if(br[nd] >= pos) bl[nd] = br[nd] = pos;
else if(bl[nd] >= pos) bl[nd] = pos;
}
upd_lazy(lf, rg, nd);
} else {
int mid = (lf + rg) / 2;
upd(lf, mid, 2*nd+1, clf, crg, op, pos);
upd(mid+1, rg, 2*nd+2, clf, crg, op, pos);
bl[nd] = max(bl[2*nd+1], bl[2*nd+2]);
br[nd] = min(br[2*nd+1], br[2*nd+2]);
}
}
int val[MXN + 1];
void fn(int lf, int rg, int nd) {
upd_lazy(lf, rg, nd);
if(lf == rg) {
val[lf] = bl[nd];
} else {
int mid = (lf + rg) / 2;
fn(lf, mid, 2*nd+1);
fn(mid+1, rg, 2*nd+2);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
build(0, n-1, 0);
for(int i=0;i<k;i++) {
upd(0, n-1, 0, left[i], right[i], op[i], height[i]);
}
fn(0, n-1, 0);
for(int i=0;i<n;i++) finalHeight[i] = val[i];
}
