#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
struct Segtree{
struct Node{
int mn = inf, mx = 0;
void apply(int x, int type){
if(type == 1){
mn = max(mn, x);
mx = max(mx, x);
}else{
mn = min(mn, x);
mx = min(mx, x);
}
}
void calibrate(){
mn = inf, mx = 0;
}
};
vector<Node> t;
int n;
void init(int _n){
n = _n;
t.resize(4 * n);
}
void push(int x){
t[x * 2].apply(t[x].mx, 1);
t[x * 2].apply(t[x].mn, 2);
t[x * 2 + 1].apply(t[x].mx, 1);
t[x * 2 + 1].apply(t[x].mn, 2);
t[x].calibrate();
}
void upd(int x, int l, int r, int ql, int qr, int val, int type){
if(l > qr || ql > r) return;
if(ql <= l && r <= qr){
//cout << l << ' ' << r << ' ' << val << ' ' << type << endl;
t[x].apply(val, type);
// cout << t[x].mx << endl;
return;
}
push(x);
int m = (l + r) / 2;
upd(x * 2, l, m, ql, qr, val, type);
upd(x * 2 + 1, m + 1, r, ql, qr, val, type);
}
void finish(vector<int> &ans, int x, int l, int r){
if(l == r){
//t[x].apply(t[x].mn, 2);
ans[l] = t[x].mx;
return;
}
push(x);
int m = (l + r) / 2;
finish(ans, x * 2, l, m); finish(ans, x * 2 + 1, m + 1, r);
}
//interface
void upd(int l, int r, int val, int type){
upd(1, 0, n - 1, l, r, val, type);
}
void finish(vector<int> &ans){
finish(ans, 1, 0, n - 1);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int ans[]){
Segtree t;
t.init(n);
vector<int> an(n);
for(int i = 0; i < k; i ++){
t.upd(left[i], right[i], height[i], op[i]);
// t.finish(an);
// for(int j = 0; j < n; j ++)cout << an[j] << ' ';
// cout << endl;
}
t.finish(an);
for(int i = 0; i < n; i ++){
ans[i] = an[i];
}
}
