#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int lazyMax[8000005], lazyMin[8000005];
vector<int> vec;
void build(int i, int l, int r)
{
lazyMax[i]=-1;
lazyMin[i]=-1;
if (l==r)
return;
int mid=(l+r)/2;
build(i*2, l, mid);
build(i*2+1, mid+1, r);
}
void push(int i, int op, int h)
{
if (op==1)
{
if (lazyMax[i]!=-1)
lazyMax[i]=max(lazyMax[i], h);
else
lazyMax[i]=h;
if (lazyMin[i]!=-1)
lazyMin[i]=max(lazyMin[i], h);
}
else
{
if (lazyMax[i]!=-1)
lazyMax[i]=min(lazyMax[i], h);
if (lazyMin[i]!=-1)
lazyMin[i]=min(lazyMin[i], h);
else
lazyMin[i]=h;
}
}
void update(int i, int l, int r, int op, int ql, int qr, int h)
{
// cout << "update " << i << ' ' << l << ' ' << r << ' ' << op << ' ' << ql << ' ' << qr << ' ' << h << '\n';
if (ql<=l && r<=qr)
{
// cout << "updated: " << l << "-" << r << " from " << lazyMax[i] << ' ' << lazyMin[i] << " to ";
push(i, op, h);
// cout << lazyMax[i] << " " << lazyMin[i] << '\n';
return;
}
// cout << "push " << lazyMax[i] << " and " << lazyMin[i] << " into [" << l << "-" << (l+r)/2 << "] and [" << (l+r)/2+1 << "-" << r << "]" << '\n';
if (lazyMax[i]!=-1)
{
push(i*2, 1, lazyMax[i]);
push(i*2+1, 1, lazyMax[i]);
lazyMax[i]=-1;
}
if (lazyMin[i]!=-1)
{
push(i*2, 2, lazyMin[i]);
push(i*2+1, 2, lazyMin[i]);
lazyMin[i]=-1;
}
int mid=(l+r)/2;
if (l<=qr && ql<=mid)
update(i*2, l, mid, op, ql, qr, h);
if (mid+1<=qr && ql<=r)
update(i*2+1, mid+1, r, op, ql, qr, h);
}
void query(int i, int l, int r)
{
// cout << "query " << i << ' ' << l << ' ' << r << '\n';
if (l==r)
{
vec.push_back(max(0, lazyMax[i]));
return;
}
// cout << "push " << lazyMax[i] << " and " << lazyMin[i] << " into [" << l << "-" << (l+r)/2 << "] and [" << (l+r)/2+1 << "-" << r << "]" << '\n';
if (lazyMax[i]!=-1)
{
push(i*2, 1, lazyMax[i]);
push(i*2+1, 1, lazyMax[i]);
lazyMax[i]=-1;
}
if (lazyMin[i]!=-1)
{
push(i*2, 2, lazyMin[i]);
push(i*2+1, 2, lazyMin[i]);
lazyMin[i]=-1;
}
int mid=(l+r)/2;
query(i*2, l, mid);
query(i*2+1, mid+1, r);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int fh[])
{
build(1, 0, n-1);
for (int i=0; i<k; i++)
// {
update(1, 0, n-1, op[i], l[i], r[i], h[i]);
// query(1, 0, n-1);
// cout << "vec: ";
// for (int j=0; j<n; j++)
// cout << vec[j] << ' ';
// cout << '\n';
// vec.clear();
// }
query(1, 0, n-1);
for (int i=0; i<n; i++)
fh[i]=vec[i];
}
