#include "wall.h"
#include <algorithm>
#include <iostream>
#include <random>
#include <chrono>
using namespace std;
using llong = long long;
#define BUGO(x) cerr << #x << " = " << (x) << '\n';
#define BUGOARR(a) {cerr << #a << ": "; for (auto i: a) cerr << i << ' '; cerr << '\n';}
#ifndef MANSON
#define BUGO(x)
#define BUGOARR(x)
#endif
ostream& operator<<(ostream& out, const pair<auto, auto>& p) {
out << "{" << p.first << ", " << p.second << "}";
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
const int maxN = 2'000'000;
struct Upd {
pair<int, char> a, b;
Upd()
: a(0, 'U')
, b(1000'000'000, 'D')
{}
};
Upd operator+(Upd l, pair<int, char> i) {
if (l.b.second == i.second) {
if (i.second == 'U' && i.first > l.b.first) l.b = i;
if (i.second == 'D' && i.first < l.b.first) l.b = i;
return l;
}
if (l.b.second == 'U') {
if (i.first <= l.b.first || (l.a.first > l.b.first && i.first < l.a.first)) {
l.a = l.b;
l.b = i;
}
}
else if (i.first >= l.b.first || (l.a.first < l.b.first && i.first > l.a.first)) {
l.a = l.b;
l.b = i;
}
return l;
}
Upd operator+(Upd l, const Upd& r) { return l + r.a + r.b; }
Upd lazy[4 * maxN];
inline void Push(int v)
{
if (v * 2 + 1 < 4 * maxN) {
lazy[v * 2] = lazy[v * 2] + lazy[v];
lazy[v * 2 + 1] = lazy[v * 2 + 1] + lazy[v];
}
lazy[v] = Upd();
}
void Update(int v, int vl, int vr, int l, int r, const pair<int, char>& upd)
{
if (l > vr || vl > r) return;
if (l <= vl && vr <= r) {
lazy[v] = lazy[v] + upd;
return;
}
Push(v);
int vm = (vl + vr) / 2;
Update(v * 2, vl, vm, l, r, upd);
Update(v * 2 + 1, vm + 1, vr, l, r, upd);
}
Upd Get(int v, int vl, int vr, int i)
{
if (vl == vr)
return lazy[v];
int vm = (vl + vr) / 2;
if (i <= vm)
return Get(v * 2, vl, vm, i) + lazy[v];
return Get(v * 2 + 1, vm + 1, vr, i) + lazy[v];
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int ans[])
{
for (int i = 0; i < k; ++i)
Update(1, 0, n - 1, left[i], right[i], make_pair(height[i], op[i] == 1 ? 'U' : 'D'));
for (int i = 0; i < n; ++i)
{
Upd upd = Get(1, 0, n - 1, i);
ans[i] = 0;
for (const pair<int, char>& x: {upd.a, upd.b})
if (x.second == 'U')
ans[i] = max(ans[i], x.first);
else
ans[i] = min(ans[i], x.first);
}
}
