#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "/home/fuad/cp/dbg.h"
#else
#define dbg(x...)
#endif
const int N = 2000010;
pair<int,int> T[4*N];
void updMn(int l, int r, int tl, int tr, int v, int p, int d);
void updMx(int l, int r, int tl, int tr, int v, int p, int d);
void updMn(int l, int r, int tl, int tr, int v, int p, int d=0) {
if(l>r)return;
if(l==tl and r==tr) {
T[v].first=min(T[v].first,p);
T[v].second=min(T[v].second,T[v].first);
return;
}
int tm=(tl+tr)/2;
updMn(tl,tm,tl,tm,2*v,T[v].first, 1);
updMn(tm+1,tr,tm+1,tr,2*v+1,T[v].first, 1);
updMx(tl,tm,tl,tm,2*v,T[v].second, 1);
updMx(tm+1,tr,tm+1,tr,2*v+1,T[v].second, 1);
T[v]={2e9,0};
updMn(l,min(r,tm), tl, tm, 2*v, p);
updMn(max(l,tm+1),r, tm+1, tr, 2*v+1, p);
}
void updMx(int l, int r, int tl, int tr, int v, int p, int d=0) {
if(l>r)return;
if(l==tl and r==tr) {
T[v].second=max(T[v].second,p);
T[v].first=max(T[v].first,T[v].second);
return;
}
int tm=(tl+tr)/2;
updMn(tl,tm,tl,tm,2*v,T[v].first, 1);
updMn(tm+1,tr,tm+1,tr,2*v+1,T[v].first, 1);
updMx(tl,tm,tl,tm,2*v,T[v].second, 1);
updMx(tm+1,tr,tm+1,tr,2*v+1,T[v].second, 1);
T[v]={2e9,0};
updMx(l,min(r,tm), tl, tm, 2*v, p);
updMx(max(l,tm+1),r, tm+1, tr, 2*v+1, p);
}
int get(int tl, int tr, int v, int p) {
if(tl == tr and tl==p) {
return min(T[v].first,T[v].second);
}
int tm=(tl+tr)/2;
updMn(tl,tm,tl,tm,2*v,T[v].first, 1);
updMn(tm+1,tr,tm+1,tr,2*v+1,T[v].first, 1);
updMx(tl,tm,tl,tm,2*v,T[v].second, 1);
updMx(tm+1,tr,tm+1,tr,2*v+1,T[v].second, 1);
if(p<=tm) {
return get(tl,tm,2*v,p);
}
return get(tm+1,tr,2*v+1,p);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i =0;i<4*N;i++)T[i]={2e9,0};
for(int i = 0;i<k;i++) {
if(op[i]==1) {
updMx(left[i],right[i],0,n-1,1,height[i]);
}
else {
updMn(left[i],right[i],0,n-1,1,height[i]);
}
}
for(int i = 0;i<n;i++) {
finalHeight[i]=get(0,n-1,1,i);
}
}
