#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
pair<int, int> st[8000001];
int r[2000001];
void lazy(ll xf, ll lf, ll rf){
if(lf==rf)return;
st[xf*2].F=min(st[xf*2].F, st[xf].S);
st[xf*2].F=max(st[xf*2].F, st[xf].F);
st[xf*2].S=max(st[xf*2].F, min(st[xf*2].S, st[xf].S));
st[xf*2+1].F=min(st[xf*2+1].F, st[xf].S);
st[xf*2+1].F=max(st[xf*2+1].F, st[xf].F);
st[xf*2+1].S=max(st[xf*2+1].F, min(st[xf*2+1].S, st[xf].S));
st[xf]={0, 1000000};
return;
}
void update1(int xf, int lf, int rf, int ol, int od, int v){
lazy(xf, lf, rf);
if(rf<ol||lf>od)return;
if(ol<=lf&&rf<=od){
if(lf==rf){
st[xf].F=max(st[xf].F, v);
st[xf].S=max(st[xf].S, v);
return;
}
st[xf].F=v;
lazy(xf, lf, rf);
return;
}
update1(xf*2, lf, (lf+rf)/2, ol, od, v);
update1(xf*2+1, (lf+rf)/2+1, rf, ol, od, v);
return ;
}
void update2(int xf, int lf, int rf, int ol, int od, int v){
lazy(xf, lf, rf);
if(rf<ol||lf>od)return;
if(ol<=lf&&rf<=od){
if(lf==rf){
st[xf].F=min(st[xf].F, v);
st[xf].S=min(st[xf].S, v);
return;
}
st[xf].S=v;
lazy(xf, lf, rf);
return;
}
update2(xf*2, lf, (lf+rf)/2, ol, od, v);
update2(xf*2+1, (lf+rf)/2+1, rf, ol, od, v);
return ;
}
void rbuild(int xf, int lf, int rf){
lazy(xf, lf, rf);
if(lf==rf){
r[lf]=st[xf].F;
return;
}
rbuild(xf*2, lf, (lf+rf)/2);
rbuild(xf*2+1, (lf+rf)/2+1, rf);
return ;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0; i<=4*n; i++)st[i].S=1000000;
for(int i=0; i<k; i++){
if(op[i]==1)update1(1, 1, n, left[i]+1, right[i]+1, height[i]);
else update2(1, 1, n, left[i]+1, right[i]+1, height[i]);
}
rbuild(1, 1, n);
for(int i=0; i<n; i++){
finalHeight[i]=r[i+1];
}
return;
}
