#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
// #define cerr if (false) cerr
const int OO = (int)1e18;
struct Segtree {
int numleaves;
// lo: build
// hi: cut
vector<pair<int,int>> tree;
Segtree (int n) {
numleaves = 1;
while (numleaves < n) numleaves *= 2;
tree.assign(2*numleaves, pair<int,int>{0, 0});
}
pair<int,int> combine(pair<int,int> newInter, pair<int,int> oldInter) {
if (newInter.first > oldInter.second) {
return pair<int,int>{newInter.first, newInter.first};
}
else if (oldInter.first > newInter.second) {
return pair<int,int>{newInter.second, newInter.second};
}
else {
return pair<int,int>{max(newInter.first, oldInter.first), min(newInter.second, oldInter.second)};
}
}
void pushdown (int node) {
if (2*node+1 < 2*numleaves) {
tree[2*node] = combine(tree[node], tree[2*node]);
tree[2*node+1] = combine(tree[node], tree[2*node+1]);
}
}
int get (int node, int nL, int nR, int target) {
pushdown(node);
if (node >= numleaves) {
return tree[node].first;
}
else {
int nMid = nL + (nR - nL) / 2;
if (nL <= target && target <= nMid) {
return get(2*node, nL, nMid, target);
}
else {
return get(2*node+1, nMid+1, nR, target);
}
}
}
int get (int target) {
return get(1, 0, numleaves-1, target);
}
void update (int node, int nL, int nR, int qL, int qR, pair<int,int> newInter) {
pushdown(node);
if (qL <= nL && nR <= qR) {
tree[node] = combine(newInter, tree[node]);
pushdown(node);
}
else if (nR < qL || qR < nL) {
return;
}
else {
int nMid = nL + (nR - nL) / 2;
update(2*node, nL, nMid, qL, qR, newInter);
update(2*node+1, nMid+1, nR, qL, qR, newInter);
tree[node] = pair<int,int>{min(tree[2*node].first, tree[2*node+1].first), max(tree[2*node].second, tree[2*node+1].second)};
}
}
void update (int qL, int qR, pair<int,int> newInter) {
update(1, 0, numleaves-1, qL, qR, newInter);
}
};
void buildWall(int N, int Q, int typeQ[], int leftQ[], int rightQ[], int heightQ[], int finalHeight[]){
Segtree wall(N);
for (int q = 0; q < Q; q++) {
if (typeQ[q] == 1) { // build
wall.update(leftQ[q], rightQ[q], pair<int,int>{heightQ[q], OO});
}
else { // cut
wall.update(leftQ[q], rightQ[q], pair<int,int>{0, heightQ[q]});
}
}
for (int i = 0; i < N; i++) {
finalHeight[i] = wall.get(i);
}
}
