#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
void print(long long t) { cerr << t; }
void print(int t) { cerr << t; }
void print(string t) { cerr << t; }
void print(char t) { cerr << t; }
void print(double t) { cerr << t; }
void print(long double t) { cerr << t; }
void print(unsigned long long t) { cerr << t; }
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[], V n) { cerr << "["; for (int i = 0; i < n; i++) { cerr << v[i] << " "; } cerr << "]"; }
template <class T, class V> void print(pair <T, V> p) { cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}"; }
template <class T> void print(vector <T> v) { cerr << "[ "; for (T i : v) { print(i); cerr << " "; } cerr << "]"; }
template <class T> void print(set <T> v) { cerr << "[ "; for (T i : v) { print(i); cerr << " "; } cerr << "]"; }
template <class T> void print(multiset <T> v) { cerr << "[ "; for (T i : v) { print(i); cerr << " "; } cerr << "]"; }
template <class T, class V> void print(map <T, V> v) { cerr << "[ "; for (auto i : v) { print(i); cerr << " "; } cerr << "]"; }
#define ll long long
struct segtree {
struct Node {
ll mn, mx, lazy;
};
vector<Node>stree;
int size = 1;
void init(int n) {
while (size < n) size <<= 1;
stree.assign(4 * size, { 0, 0, -1 });
}
void push(int x, int lx, int rx) {
if (rx - lx == 1 || stree[x].lazy == -1) return;
stree[2 * x + 1].lazy = stree[x].lazy;
stree[2 * x + 2].lazy = stree[x].lazy;
int m = (lx + rx) / 2;
stree[2 * x + 1].mn = stree[2 * x + 1].mx = stree[x].lazy;
stree[2 * x + 2].mn = stree[2 * x + 2].mx = stree[x].lazy;
stree[x].lazy = -1;
}
void upd(int l, int r, int v, int x, int lx, int rx) {
push(x, lx, rx);
if (lx >= r || rx <= l) return;
if (lx >= l && rx <= r) {
stree[x].lazy = v;
stree[x].mn = v;
stree[x].mx = v;
return;
}
int m = (lx + rx) / 2;
upd(l, r, v, 2 * x + 1, lx, m);
upd(l, r, v, 2 * x + 2, m, rx);
stree[x].mx = max(stree[2 * x + 1].mx, stree[2 * x + 2].mx);
stree[x].mn = min(stree[2 * x + 1].mn, stree[2 * x + 2].mn);
}
void upd_add(int l, int r, int h, int x, int lx, int rx) {
push(x, lx, rx);
if (lx >= r || rx <= l) return;
if (lx >= l && rx <= r && stree[x].mx <= h) {
dbg(lx);
dbg(rx);
dbg(h);
upd(lx, rx, h);
return;
}
else if (lx >= l && rx <= r && stree[x].mn > h) {
return;
}
int m = (lx + rx) / 2;
upd_add(l, r, h, 2 * x + 1, lx, m);
upd_add(l, r, h, 2 * x + 2, m, rx);
}
void upd_del(int l, int r, int h, int x, int lx, int rx) {
push(x, lx, rx);
if (lx >= r || rx <= l) return;
if (lx >= l && rx <= r && stree[x].mn >= h) {
upd(lx, rx, h);
return;
}
else if(lx >= l && rx <= r && stree[x].mx < h){
return;
}
int m = (lx + rx) / 2;
upd_del(l, r, h, 2 * x + 1, lx, m);
upd_del(l, r, h, 2 * x + 2, m, rx);
}
ll qry(int l, int r, int x, int lx, int rx) {
push(x, lx, rx);
if (lx >= r || rx <= l) return 0;
if (lx >= l && rx <= r) return stree[x].mx;
int m = (lx + rx) / 2;
return max(qry(l, r, 2 * x + 1, lx, m), qry(l, r, 2 * x + 2, m, rx));
}
void upd(int l, int r, int v) {
upd(l, r, v, 0, 0, size);
}
ll qry(int l, int r) {
return qry(l, r, 0, 0, size);
}
void upd_add(int l, int r, int h) {
upd_add(l, r, h, 0, 0, size);
}
void upd_del(int l, int r, int h) {
upd_del(l, r, h, 0, 0, size);
}
}st;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
st.init(n);
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
st.upd_add(left[i], right[i] + 1, height[i]);
}
else {
st.upd_del(left[i], right[i] + 1, height[i]);
}
}
for (int i = 0; i < n; i++) {
finalHeight[i] = st.qry(i, i + 1);
}
}
