#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int MAXN = 2e6 + 10;
struct node
{
int maxVal, minVal, lz;
node(int MX = 0, int MN = 0, int LZ = -1) : maxVal(MX), minVal(MN), lz(LZ) {}
node operator+ (node outro)
{
return node(max(maxVal, outro.maxVal), min(minVal, outro.minVal));
}
};
array<node, 4*MAXN> seg;
void refresh(int pos, int ini, int fim)
{
if (seg[pos].lz == -1) return;
int x = seg[pos].lz; seg[pos].lz = -1;
seg[pos].maxVal = seg[pos].minVal = x;
if (ini == fim) return;
int e = 2*pos, d = e+1;
seg[e].lz = seg[d].lz = x;
}
void updateAdd(int pos, int ini, int fim, int p, int q, int val)
{
refresh(pos, ini, fim);
if (q < ini || p > fim || seg[pos].minVal >= val) return;
if (p <= ini && fim <= q && seg[pos].maxVal <= val)
{
seg[pos].lz = val;
refresh(pos, ini, fim);
return;
}
int m = (ini + fim) >> 1;
int e = 2*pos, d = e+1;
updateAdd(e, ini, m, p, q, val);
updateAdd(d, m+1, fim, p, q, val);
seg[pos] = seg[e] + seg[d];
}
void updateRem(int pos, int ini, int fim, int p, int q, int val)
{
refresh(pos, ini, fim);
if (q < ini || p > fim || seg[pos].maxVal <= val) return;
if (p <= ini && fim <= q && seg[pos].minVal >= val)
{
seg[pos].lz = val;
refresh(pos, ini, fim);
return;
}
int m = (ini + fim) >> 1;
int e = 2*pos, d = e+1;
updateRem(e, ini, m, p, q, val);
updateRem(d, m+1, fim, p, q, val);
seg[pos] = seg[e] + seg[d];
}
node query(int pos, int ini, int fim, int p, int q)
{
refresh(pos, ini, fim);
if (q < ini || p > fim) return node(0, (int)1e9);
if (p <= ini && fim <= q) return seg[pos];
int m = (ini + fim) >> 1;
int e = 2*pos, d = e+1;
return (query(e, ini, m, p, q) + query(d, m+1, fim, p, q));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for (int i = 0; i < k; i++)
{
if (op[i] == 1) updateAdd(1, 0, n-1, left[i], right[i], height[i]);
else updateRem(1, 0, n-1, left[i], right[i], height[i]);
}
for (int i = 0; i < n; i++) finalHeight[i] = query(1, 0, n-1, i, i).maxVal;
}
