#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int N=100009;
int a,b,c,d,e,i,j,ii,jj,zx,xc,ans[2000009],tes,t,tp,l,r,zl,zr,za,segl[8000009],segr[8000009],segt[8000009];
void CHANGE(int rr, int l, int r, int t){
if(t!=N){
segl[rr]=-N;segr[rr]=N;segt[rr]=t;
return;
}
if(segt[rr]!=N){
segt[rr]=max(segt[rr],l);
segt[rr]=min(segt[rr],r);
return;
}
if(l>segr[rr]){
segl[rr]=-N;segr[rr]=N;segt[rr]=l;
return;
}
if(r<segl[rr]){
segl[rr]=-N;segr[rr]=N;segt[rr]=r;
return;
}
segl[rr]=max(segl[rr],l);
segr[rr]=min(segr[rr],r);
}
void pushdown(int q, int w, int rr){
CHANGE(rr*2,segl[rr],segr[rr],segt[rr]);
CHANGE(rr*2+1,segl[rr],segr[rr],segt[rr]);
segl[rr]=-N;segr[rr]=N;segt[rr]=N;
}
void upd(int q, int w, int rr){
if(q>r||w<l) return;
if(q>=l&&w<=r){
CHANGE(rr,zl,zr,N);
return;
}
pushdown(q,w,rr);
upd(q,(q+w)/2,rr*2);
upd((q+w)/2+1,w,rr*2+1);
}
void buildWall(int Nn, int Kk, int Oop[], int Lleft[], int Rright[], int Hheight[], int finalHeight[]){
a=Nn;tes=Kk;
za=1;
while(za<a) za*=2;
for(i=0; i<=za*2; i++){
segl[i]=-N;segr[i]=N;segt[i]=N;
}
for(t=1; t<=tes; t++){
tp=Oop[t-1];
if(tp==2){
l=Lleft[t-1]+1;r=Rright[t-1]+1;zl=-N;zr=Hheight[t-1];
upd(1,za,1);
}else{
l=Lleft[t-1]+1;r=Rright[t-1]+1;zl=Hheight[t-1];zr=N;
upd(1,za,1);
}
}
for(i=1; i<=a; i++){
c=za+i-1;zx=0;
while(c!=0){
if(segt[c]!=N){
zx=segt[c];
c/=2;
continue;
}
zx=max(zx,segl[c]);
zx=min(zx,segr[c]);
c/=2;
}
ans[i]=zx;
}
//
for(i=1; i<=a; i++){
finalHeight[i-1]=ans[i];
}
}
