#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int MAXN=4194305;
int sz=1;
int a[MAXN],b[MAXN];//alazy[MAXN],blazy[MAXN];
void push(int v){
a[2*v]=max(b[v*2],min(a[v],a[2*v]));
// alazy[2*v]=min(alazy[v],alazy[2*v]);
a[2*v+1]=max(b[v*2+1],min(a[v],a[2*v+1]));
// alazy[2*v+1]=min(alazy[v],alazy[2*v+1]);
// a[v]=alazy[v];
b[2*v]=min(a[v*2],max(b[v],b[2*v]));
// blazy[2*v]=max(blazy[v],blazy[2*v]);
b[2*v+1]=min(a[v*2+1],max(b[v],b[2*v+1]));
// blazy[2*v+1]=max(blazy[v],blazy[2*v+1]);
// b[v]=blazy[v];
}
void update1(int v, int tl, int tr, int l, int r, int val){
// cout << v << ' ' << tl << ' ' << tr << ' ' << l << ' ' << r << ' ' << val << '\n';
if(l>r)return;
if(tl==l&&tr==r){
b[v]=min(a[v],max(b[v],val));
}else{
push(v);
int mid=(tl+tr)/2;
update1(v*2,tl,mid,l,min(mid,r),val);
update1(v*2+1,mid+1,tr,max(mid+1,l),r,val);
}
}
void update2(int v, int tl, int tr, int l, int r, int val){
// cout << v << ' ' << tl << ' ' << tr << ' ' << l << ' ' << r << ' ' << val << '\n';
if(l>r)return;
if(tl==l&&tr==r){
a[v]=max(b[v],min(a[v],val));
}else{
push(v);
int mid=(tl+tr)/2;
update2(v*2,tl,mid,l,min(mid,r),val);
update2(v*2+1,mid+1,tr,max(mid+1,l),r,val);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
while(sz<n)sz<<=1;
for(int i=1;i<2*sz;i++){
a[i]=1000001;
b[i]=0;
}
// cout << "fdas";
for(int i=k-1;i>=0;i--){
if(op[i]==1)update1(1,1,sz,left[i]+1,right[i]+1,height[i]);
else update2(1,1,sz,left[i]+1,right[i]+1,height[i]);
for(int i=1;i<sz;i++)push(i);
// cout << height[i];
// for(int i=0;i<n;i++)cout << '(' << a[i+sz] << ' ' << b[i+sz] << ')';
// cout << '\n';
}
// cout << "adf";
for(int i=0;i<n;i++)finalHeight[i]=b[i+sz];
return;
}
