#include "wall.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=2e6+5;
int res[nx], lmax[nx<<2], lmin[nx<<2];
void down(int id)
{
if(lmax[id]!=lmin[id])
return;
lmin[id<<1]=lmax[id<<1]=lmin[id];
lmin[id<<1|1]=lmax[id<<1|1]=lmin[id];
}
void update(int id, int l, int r, int u, int v, int val)
{
if(val<=lmin[id] || l>v || r<u)
return;
if(l>=u && r<=v && val>lmax[id])
{
lmin[id]=lmax[id]=val;
return;
}
int mid=(l+r)>>1;
down(id);
update(id<<1, l, mid, u, v, val);
update(id<<1|1, mid+1, r, u, v, val);
lmin[id]=min(lmin[id<<1], lmin[id<<1|1]);
lmax[id]=max(lmax[id<<1], lmax[id<<1|1]);
}
void update1(int id, int l, int r, int u, int v, int val)
{
if(val>=lmax[id] || l>v || r<u)
return;
if(l>=u && r<=v && val<lmin[id])
{
lmin[id]=lmax[id]=val;
return;
}
int mid=(l+r)>>1;
down(id);
update1(id<<1, l, mid, u, v, val);
update1(id<<1|1, mid+1, r, u, v, val);
lmin[id]=min(lmin[id<<1], lmin[id<<1|1]);
lmax[id]=max(lmax[id<<1], lmax[id<<1|1]);
}
void push(int id, int l, int r)
{
if(l==r)
{
res[l]=lmin[id];
return;
}
int mid=(l+r)/2;
down(id);
push(id<<1, l, mid);
push(id<<1|1, mid+1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for(int i = 0; i < k; i++)
{
left[i]++, right[i]++;
if(op[i]==1) update(1, 1, n, left[i], right[i], height[i]);
else update1(1, 1, n, left[i], right[i], height[i]);
}
push(1, 1, n);
for(int i = 1; i <= n; i++)
finalHeight[i-1]=res[i];
}
