#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")
#include<bits/stdc++.h>
using namespace std;
#include "wall.h"
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
ostream& operator<<(ostream &out, string str) {
for(char c : str) out << c;
return out;
}
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
return out << "(" << p.ST << ", " << p.ND << ")";
}
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
out << "{";
for(auto it = a.begin(); it != a.end(); it = next(it))
out << (it != a.begin() ? ", " : "") << *it;
return out << "}";
}
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
cerr << a << ", ";
dump(x...);
}
#ifdef DEBUG
# define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
# define debug(...) false
#endif
template<class T> int size(T && a) { return (int) a.size(); }
using LL = long long;
using PII = pair<int, int>;
struct Node {
int low = 0, high = 1e5;
int lazy_low = 0, lazy_high = 1e5;
int sz = 1;
};
struct Tree {
vector<Node> tree;
int sz = 1;
Tree(int n) {
while(sz < n)
sz *= 2;
tree.resize(sz * 2);
for(int i = sz - 1; i >= 1; i--)
tree[i].sz = tree[i * 2].sz * 2;
}
void apply(int v, int low, int high) {
auto adjust = [&](int &x) {
if(x < low) x = low;
if(high < x) x = high;
};
adjust(tree[v].low);
adjust(tree[v].high);
adjust(tree[v].lazy_low);
adjust(tree[v].lazy_high);
}
void propagate(int v) {
REP(i, 2)
apply(v * 2 + i, tree[v].lazy_low, tree[v].lazy_high);
tree[v].lazy_low = 0, tree[v].lazy_high = 1e5;
}
void update(int l, int r, int val_l, int val_r, int v = 1) {
if(l == 0 && r == tree[v].sz - 1) {
apply(v, val_l, val_r);
return;
}
propagate(v);
int m = tree[v].sz / 2;
if(r < m) update(l, r, val_l, val_r, v * 2);
else if(m <= l) update(l - m, r - m, val_l, val_r, v * 2 + 1);
else {
update(l, m - 1, val_l, val_r, v * 2),
update(0, r - m, val_l, val_r, v * 2 + 1);
}
}
void prop_all(int v = 1) {
if(tree[v].sz == 1) return;
propagate(v);
REP(i, 2)
prop_all(v * 2 + i);
}
int get(int v) {
return tree[v + sz].low;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
Tree tree(n);
REP(i, k) {
int val_l = (op[i] == 1 ? height[i] : 0);
int val_r = (op[i] == 2 ? height[i] : 1e5);
tree.update(left[i], right[i], val_l, val_r);
}
tree.prop_all();
REP(i, n) finalHeight[i] = tree.get(i);
}
