#include "wall.h"
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
struct Seg {
int pot;
vector<ii> T, L;
void init(int n) {
pot = 1;
while(pot < n) pot <<= 1;
T = vector<ii>(pot << 1, {0, 1e5});
L = vector<ii>(pot << 1, {0, 1e5});
}
ii merge(ii f, ii g) {
ii ret;
if(g.x >= f.y) return {f.y, f.y};
if(g.y <= f.x) return {f.x, f.x};
return {max(g.x, f.x), min(g.y, f.y)};
}
void prop(int x) {
T[x] = merge(L[x], T[x]);
if(x < pot) L[x * 2] = merge(L[x], L[x * 2]);
if(x < pot) L[x * 2 + 1] = merge(L[x], L[x * 2 + 1]);
L[x] = {0, 1e5};
}
void update(int x, int lo, int hi, int a, int b, ii f) {
prop(x);
if(hi < a || b < lo) return;
if(a <= lo && hi <= b) {
L[x] = merge(f, L[x]);
prop(x);
return;
}
int mid = (lo + hi) / 2;
update(x * 2, lo, mid, a, b, f);
update(x * 2 + 1, mid + 1, hi, a, b, f);
}
void add(int lo, int hi, ii f) {update(1, 0, pot - 1, lo, hi, f);}
int get(int x) {return T[x + pot].x;}
} S;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
S.init(n);
for(int i = 0;i < k;i++) {
if(op[i] == 1)
S.add(left[i], right[i], {height[i], 1e5});
if(op[i] == 2)
S.add(left[i], right[i], {0, height[i]});
}
for(int i = 0;i < n;i++)
S.add(i, i, {0, 1e5});
for(int i = 0;i < n;i++)
finalHeight[i] = S.get(i);
}
