#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int rgt = (1 << 21);
const int sz = (1<<22)+5;
int u[sz], d[sz];
void combine(int id, int down, int up)
{
d[id] = min(d[id],down);
d[id] = max(d[id],up);
u[id] = max(u[id],up);
u[id] = min(u[id],down);
}
void process(int id, char mode, int h)
{
if(mode == 'u')
{
d[id] = max(d[id],h);
u[id] = max(u[id],h);
}
else
{
d[id] = min(d[id],h);
u[id] = min(u[id],h);
}
}
void update(int id, int l, int r, int x, int y, int h, char mode)
{
if(x > r || y < l)
return;
if(x <= l && y >= r)
{
process(id,mode,h);
return;
}
combine(2*id,d[id],u[id]);
combine(2*id+1,d[id],u[id]);
d[id] = sz; u[id] = 0;
int m = (l+r)/2;
update(2*id,l,m,x,y,h,mode);
update(2*id+1,m+1,r,x,y,h,mode);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 0; i < k; i++)
{
char mode = op[i] == 1 ? 'u' : 'd';
update(1,1,rgt,left[i]+1,right[i]+1,height[i],mode);
}
for(int i = 1; i < rgt-1; i++)
combine(2*i,d[i],u[i]), combine(2*i+1,d[i],u[i]);
for(int i = rgt; i <= rgt+n-1; i++)
finalHeight[i-rgt] = min(d[i],u[i]);
}
