#include "wall.h"
#include<cstdio>
#include<algorithm>
using namespace std;
int mi[8000000], ma[8000000];
int *dap;
void update(int lo, int hi, int val, int node, int x, int y, int p) {
if (hi < x || y < lo)return;
if (lo <= x && y <= hi) {
if (p == 1) {
mi[node] = max(mi[node], val);
ma[node] = max(ma[node], val);
}
else if (p == 2)
{
mi[node] = min(mi[node], val);
ma[node] = min(ma[node], val);
}
if (x == y)
dap[x] = ma[node];
return;
}
int ll = node * 2;
int rr = node * 2 + 1;
int mid = (x + y) / 2;
mi[ll] = min(mi[ll], mi[node]); mi[rr] = min(mi[rr], mi[node]);
ma[ll] = min(ma[ll], mi[node]); ma[rr] = min(ma[rr], mi[node]);
mi[ll] = max(mi[ll], ma[node]); mi[rr] = max(mi[rr], ma[node]);
ma[ll] = max(ma[ll], ma[node]); ma[rr] = max(ma[rr], ma[node]);
ma[node] = 0; mi[node] = 1234567890;
update(lo, hi, val, node * 2, x, mid, p);
update(lo, hi, val, node * 2 + 1, mid + 1, y, p);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
dap = finalHeight;
for (int i = 0; i < k; ++i) {
update(left[i], right[i], height[i], 1, 0, n - 1, op[i]);
}
for (int i = 0; i < n; ++i)
update(i, i, 0, 1, 0, n - 1, 0);
return;
}
