#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct node{
int s,e,m;
array<int, 2> v;
node *l, *r;
node(int S,int E){
s=S,e=E,m=(s+e)/2;
v[0]=0, v[1]=1e6; // 0 is chmax, 1 is chmin
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void prop(){
if(s!=e){
l->v[0]=max(l->v[0], v[0]);
l->v[0]=min(l->v[0], v[1]);
l->v[1]=min(l->v[1], v[1]);
l->v[1]=max(l->v[1], v[0]);
r->v[0]=max(r->v[0], v[0]);
r->v[0]=min(r->v[0], v[1]);
r->v[1]=min(r->v[1], v[1]);
r->v[1]=max(r->v[1], v[0]);
v[0]=0,v[1]=1e6;
}
}
void upd(int S, int E, int nv, int type){
prop();
if(s==S and e==E){
if(type==1){
v[1]=min(v[1], nv);
v[0]=min(v[0], nv);
}
else {
v[0]=max(v[0], nv);
v[1]=max(v[1], nv);
}
//~ printf("seg %d to %d, v[0] %d v[1] %d lz[0] %d lz[1] %d\n", s,e,v[0],v[1], lz[0], lz[1]);
return;
}
if(E <= m)return l->upd(S,E,nv,type);
if(S > m)return r->upd(S,E,nv,type);
l->upd(S,m,nv,type);
r->upd(m+1, E, nv, type);
}
int qry(int x){
//~ printf("q seg %d to %d, v[0] %d v[1] %d, lz[0] %d, lz[1] %d\n", s, e,v[0],v[1], lz[0], lz[1]);
prop();
if(s==e){
assert(s==x);
return min(v[1], v[0]);
}
if(x<=m)return l->qry(x);
else return r->qry(x);
}
} *root;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
root=new node(0, n-1);
for(int i=0;i<k;i++){
if(op[i]==2)root->upd(left[i],right[i], height[i],1);
else root->upd(left[i],right[i],height[i],0);
//~ for(int j=0;j<n;j++){
//~ cout<<root->qry(j)<<" ";
//~ }
//~ cout<<endl<<endl;
}
for(int i=0;i<n;i++){
int ret=root->qry(i);
finalHeight[i]=(ret==1e6? 0:ret);
}
return;
}
