#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int N = 2e6+3;
int mn[4*N], mx[4*N], f[4*N];
int inf=100000001;
void inter(int a, int b, int c, int d, int &lft, int &rgt){
if(a>d){
lft=rgt=a;
}
else if(b<c){
lft=rgt=b;
}
else{
lft=max(a, c);
rgt=min(b, d);
}
}
void Push(int node){
int lc=2*node+1;
int rc=2*node+2;
inter(mx[node], mn[node], mx[lc], mn[lc], mx[lc], mn[lc]);
inter(mx[node], mn[node], mx[rc], mn[rc], mx[rc], mn[rc]);
f[lc]=f[rc]=f[node];
mn[node]=inf;
mx[node]=0;
}
void mxUpd(int node, int l, int r, int L, int R, int val){
if(l>r || l>R | r<L)return;
if(l>=L && r<=R){
inter(val, inf, mx[node], mn[node], mx[node], mn[node]);
if(mn[node]==inf)f[node]=0;
else f[node]=1;
return;
}
Push(node);
int mid=(l+r)/2;
mxUpd(2*node+1, l, mid, L, R, val);
mxUpd(2*node+2, mid+1, r, L, R, val);
}
void mnUpd(int node, int l, int r, int L, int R, int val){
if(l>r || l>R || r<L)return;
if(l>=L && r<=R){
inter(0, val, mx[node], mn[node], mx[node], mn[node]);
if(mx[node]==0)f[node]=1;
else f[node]=0;
return;
}
Push(node);
int mid=(l+r)/2;
mnUpd(2*node+1, l, mid, L, R, val);
mnUpd(2*node+2, mid+1, r, L, R, val);
}
int Get(int node, int l, int r, int ind){
if(l>ind || r<ind)return 0;
if(l==r){
if(f[node])return max(mx[node], mn[node]);
else return min(mn[node], mx[node]);
}
Push(node);
int mid=(l+r)/2;
return Get(2*node+1, l, mid, ind)+Get(2*node+2, mid+1, r, ind);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0; i<4*N; i++)mn[i]=inf;
for(int i=0; i< k; i++){
if(op[i]==1){
mxUpd(0, 0, n-1, left[i], right[i], height[i]);
}
else{
mnUpd(0, 0, n-1, left[i], right[i], height[i]);
}
}
for(int i=0; i< n; i++){
finalHeight[i]=Get(0, 0, n-1, i);
}
return;
}
