#include "wall.h"
#include<bits/stdc++.h>
#define MAX_N 2000005
#define inf 1000005
using namespace std;
struct Tree{
int l,r,x;
}t[4*MAX_N];
void add(int x,int v,int b){
if(b==1){
if(v<=t[x].l) return;
if(t[x].l<v && t[x].r>v){
t[x].l=v;
t[x].x=1;
return;
}
t[x].l=t[x].r=v;
t[x].x=0;
}else{
if(t[x].r<=v) return;
if(t[x].l<=v && t[x].r>v){
t[x].r=v;
t[x].x=0;
return;
}
t[x].l=t[x].r=v;
t[x].x=1;
}
}
void spread(int x,int y){
if(t[x].x){
add(y,t[x].l,1);
add(y,t[x].r,2);
}else{
add(y,t[x].r,2);
add(y,t[x].l,1);
}
}
void update(int x,int l,int r,int s,int e,int v,int b){
if(l!=r){
spread(x,2*x);
spread(x,2*x+1);
t[x]={0,inf,0};
}
if(e<l || r<s) return;
if(s<=l && r<=e){
add(x,v,b);
return;
}
int mid=(l+r)>>1;
update(2*x,l,mid,s,e,v,b);
update(2*x+1,mid+1,r,s,e,v,b);
}
int calc(int x,int v,int b){
if(b==1) return (x<v?v:x);
else return (x>v?v:x);
}
int get(int x,int l,int r,int p){
if(l==r) return t[x].l;
int mid=(l+r)>>1,q;
if(p<=mid) q=get(2*x,l,mid,p);
else q=get(2*x+1,mid+1,r,p);
if(t[x].x==0) q=calc(calc(q,t[x].l,1),t[x].r,2);
else q=calc(calc(q,t[x].r,2),t[x].l,1);
return q;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
int i;
for(i=0;i<=4*n;i++) t[i]={0,inf,0};
for(i=0;i<k;i++){
update(1,0,n-1,left[i],right[i],height[i],op[i]);
}
for(i=0;i<n;i++) finalHeight[i]=get(1,0,n-1,i);
return;
}
