#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int n, cur = 0;
struct node {
int omin = 2000000000, omax = 0;
};
vector<node> t;
vector<int> sol;
void Propagate(int node) {
t[2 * node].omin = max(t[node].omax, min(t[node].omin, t[2 * node].omin));
t[2 * node].omax = min(t[node].omin, max(t[node].omax, t[2 * node].omax));
t[2 * node + 1].omin = max(t[node].omax, min(t[node].omin, t[2 * node + 1].omin));
t[2 * node + 1].omax = min(t[node].omin, max(t[node].omax, t[2 * node + 1].omax));
t[node].omin = 2000000000, t[node].omax = 0;
}
void Update(int q, int h, int posleft, int posright, int node = 1, int left = 1, int right = n) {
if (posleft <= left && right <= posright) {
if (q == 1) {
t[node].omax = max(t[node].omax, h);
t[node].omin = max(t[node].omin, t[node].omax);
}
else {
t[node].omin = min(t[node].omin, h);
t[node].omax = min(t[node].omin, t[node].omax);
}
return;
}
Propagate(node);
int m = (left + right) / 2;
if (posleft <= m)
Update(q, h, posleft, posright, 2 * node, left, m);
if (posright > m)
Update(q, h, posleft, posright, 2 * node + 1, m + 1, right);
}
void Solve(int node = 1, int left = 1, int right = n) {
if (left == right) {
sol.emplace_back(min(t[node].omin, t[node].omax));
return;
}
Propagate(node);
int m = (left + right) / 2;
Solve(2 * node, left, m);
Solve(2 * node + 1, m + 1, right);
}
void buildWall(int n, int k, int type[], int l[], int r[], int val[], int ans[]) {
t = vector<node>(4 * n);
for (int i = 0; i < k; ++i)
Update(type[i], val[i], l[i] + 1, r[i] + 1);
//Solve();
for (int i = 0; i < n; ++i)
ans[i] = sol[i];
}
