"
#include "bits/stdc++.h"
using namespace std;
struct Max_Lazy_Segment_Tree {
// update range [l; r] +x, and find sum in range [a; b]
int64_t n;
vector<int64_t> tree, lazy;
Max_Lazy_Segment_Tree(int64_t _n) {
n = _n + 5, tree.assign(n << 2, 0), lazy.assign(n << 2, 0); // init tree and lazy vectors are filled with 0
}
void relax(const int64_t &v, const int64_t &tl, const int64_t &tr) {
if (!lazy[v]) return;
tree[v] = max(tree[v], lazy[v]);
if (tl != tr) lazy[v << 1] = max(lazy[v << 1], lazy[v]), lazy[v << 1 | 1] = max(lazy[v << 1 | 1], lazy[v]);
lazy[v] = 0;
}
void update(const int64_t &v, const int64_t &tl, const int64_t &tr, const int64_t &l, const int64_t &r, const int64_t &add) {
relax(v, tl, tr);
if (l > r || tl > r || l > tr) return;
if (l <= tl && tr <= r) {
lazy[v] = max(lazy[v], add); relax(v, tl, tr);
return;
}
int64_t tm = (tl + tr) >> 1;
update(v << 1, tl, tm, l, min(r, tm), add); update(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, add);
tree[v] = max(tree[v << 1], tree[v << 1 | 1]);
}
int64_t getans(const int64_t &v, const int64_t &tl, const int64_t &tr, const int64_t &l, const int64_t &r) {
relax(v, tl, tr);
if (l > r || tl > r || l > tr) return 0;
if (l <= tl && tr <= r) return tree[v];
int64_t tm = (tl + tr) >> 1;
return max(getans(v << 1, tl, tm, l, min(r, tm)), getans(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r));
}
};
struct Min_Lazy_Segment_Tree {
// update range [l; r] +x, and find sum in range [a; b]
int64_t n;
vector<int64_t> tree, lazy;
Min_Lazy_Segment_Tree(int64_t _n) {
n = _n + 5, tree.assign(n << 2, 0), lazy.assign(n << 2, 0); // init tree and lazy vectors are filled with 0
}
void relax(const int64_t &v, const int64_t &tl, const int64_t &tr) {
if (!lazy[v]) return;
tree[v] = min(tree[v], lazy[v]);
if (tl != tr) {
if (lazy[v << 1]) lazy[v << 1] = min(lazy[v << 1], lazy[v]);
if (lazy[v << 1 | 1]) lazy[v << 1 | 1] = min(lazy[v << 1 | 1], lazy[v]);
}
lazy[v] = 0;
}
void update(const int64_t &v, const int64_t &tl, const int64_t &tr, const int64_t &l, const int64_t &r, const int64_t &add) {
relax(v, tl, tr);
if (l > r || tl > r || l > tr) return;
if (l <= tl && tr <= r) {
if (lazy[v]) lazy[v] = min(lazy[v], add);
else lazy[v] = add;
relax(v, tl, tr);
return;
}
int64_t tm = (tl + tr) >> 1;
update(v << 1, tl, tm, l, min(r, tm), add); update(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, add);
tree[v] = min(tree[v << 1], tree[v << 1 | 1]);
}
int64_t getans(const int64_t &v, const int64_t &tl, const int64_t &tr, const int64_t &l, const int64_t &r) {
relax(v, tl, tr);
if (l > r || tl > r || l > tr) return INT_MAX;
if (l <= tl && tr <= r) return tree[v];
int64_t tm = (tl + tr) >> 1;
return min(getans(v << 1, tl, tm, l, min(r, tm)), getans(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r));
}
};
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
Min_Lazy_Segment_Tree MINTREE(N + 5);
Max_Lazy_Segment_Tree MAXTREE(N + 5);
bool flag = true;
for (int i = 0; i < K; i++) {
int L = left[i], R = right[i], H = height[i]; L++, R++;
if (op[i] == 1) {
// adding
MAXTREE.update(1, 1, N, L, R, H);
} else {
// remoing
if (!flag) for (int i = 1; i <= N; i++) MINTREE.update(1, 1, N, i, i, MAXTREE.getans(1, 1, N, i, i));
flag = true;
MINTREE.update(1, 1, N, L, R, H);
}
}
for (int i = 1; i <= N; i++) finalHeight[i - 1] = MINTREE.getans(1, 1, N, i, i);
return;
}
