#include "wall.h"
#include <bits/stdc++.h>
#define N 2000002
#define INF INT_MAX
using namespace std;
int up[N*4],down[N*4],ans[N];
void build(int id,int l,int r){
if(l==r){
down[id]=INF;
return;
}
int m=l+r>>1;
build(id*2,l,m);
build(id*2+1,m+1,r);
}
void query(int id,int l,int r){
if(l==r){
ans[l]=min(up[id],down[id]);
return;
}
if(l!=r){
up[id*2]=max(up[id],up[id*2]);
up[id*2]=min(up[id*2],down[id]);
down[id*2]=min(down[id],down[id*2]);
down[id*2]=max(down[id*2],up[id]);
up[id*2+1]=max(up[id],up[id*2+1]);
up[id*2+1]=min(up[id*2+1],down[id]);
down[id*2+1]=min(down[id],down[id*2+1]);
down[id*2+1]=max(down[id*2+1],up[id]);
up[id]=0;
down[id]=INF;
}
int m=l+r>>1;
query(id*2,l,m);
query(id*2+1,m+1,r);
}
void update(int id,int l,int r,int L,int R,int op,int H){
// cout << l << ' ' << r << "\n";
if(l!=r){
up[id*2]=max(up[id],up[id*2]);
up[id*2]=min(up[id*2],down[id]);
down[id*2]=min(down[id],down[id*2]);
down[id*2]=max(down[id*2],up[id]);
up[id*2+1]=max(up[id],up[id*2+1]);
up[id*2+1]=min(up[id*2+1],down[id]);
down[id*2+1]=min(down[id],down[id*2+1]);
down[id*2+1]=max(down[id*2+1],up[id]);
up[id]=0;
down[id]=INF;
}
if(r<L || R<l){
return;
}
if(L<=l && r<=R){
if(op==1){
up[id]=max(up[id],H);
down[id]=max(down[id],H);
}
if(op==2){
up[id]=min(up[id],H);
down[id]=min(down[id],H);
}
return;
}
int m=l+r>>1;
update(id*2,l,m,L,R,op,H);
update(id*2+1,m+1,r,L,R,op,H);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
build(1,0,n-1);
for(int i=0;i<k;i++){
update(1,0,n-1,left[i],right[i],op[i],height[i]);
}
query(1,0,n-1);
for(int i=0;i<n;i++){
finalHeight[i]=ans[i];
}
}
