#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = int;
const ll INF = 1e9;
class SegTreeNode {
private:
ll l, r;
SegTreeNode *leftChild, *rightChild;
ll lowerBound, upperBound;
public:
SegTreeNode(ll l, ll r) {
this->l = l, this->r = r;
ll lowerBound = 0, upperBound = INF;
if (l == r) {
leftChild = nullptr;
rightChild = nullptr;
return;
}
ll M = (l + r) / 2;
leftChild = new SegTreeNode(l, M);
rightChild = new SegTreeNode(M + 1, r);
}
void fixBounds(ll lb, ll ub) { // this took me quite a while to get :') even looking at reflections, editorials, submissions, etc.
// basically setting the "strictest" possible bounds for the wall
upperBound = min(upperBound, ub); // if ub >= upperBound, i.e. if the "highest block" is higher than what we already have as "highest block", then idgaf
lowerBound = min(lowerBound, upperBound); // lower bound must be at most upper bound
lowerBound = max(lowerBound, lb); // if lb <= lowerBound, i.e. if the "lowest block" is lower than what we already have as "lowest", then idgaf
upperBound = max(lowerBound, upperBound); // upper bound must be at least lower bound
}
void propagate() {
if (leftChild != nullptr) {
leftChild->fixBounds(lowerBound, upperBound);
rightChild->fixBounds(lowerBound, upperBound);
lowerBound = 0, upperBound = INF;
}
}
ll query(ll i) {
if (l == r) {
return lowerBound;
}
ll M = (l + r) / 2;
propagate();
if (i <= M) return leftChild->query(i);
else return rightChild->query(i);
}
void addWall(ll ql, ll qr, ll newHeight) {
if (l > qr || r < ql) return;
if (ql <= l && r <= qr) {
fixBounds(newHeight, INF); // only from newHeight to INF now
propagate();
return;
}
ll M = (l + r) / 2;
propagate();
leftChild->addWall(ql, qr, newHeight);
rightChild->addWall(ql, qr, newHeight);
}
void removeWall(ll ql, ll qr, ll newHeight) {
if (l > qr || r < ql) return;
if (ql <= l && r <= qr) {
fixBounds(0, newHeight); // only from 0 to newHeight now
propagate();
return;
}
ll M = (l + r) / 2;
propagate();
leftChild->removeWall(ql, qr, newHeight);
rightChild->removeWall(ql, qr, newHeight);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SegTreeNode* st = new SegTreeNode(0, n - 1);
for (ll i = 0; i < k; i++) {
if (op[i] == 1) {
st->addWall(left[i], right[i], height[i]);
} else {
st->removeWall(left[i], right[i], height[i]);
}
}
for (ll i = 0; i < n; i++) {
finalHeight[i] = st->query(i);
}
}
// int main() {
// int n = 10, k = 6;
// int op[6] = {1, 2, 2, 1, 1, 2};
// int left[6] = {1, 4, 3, 0, 2, 6};
// int right[6] = {8, 9, 6, 5, 2, 7};
// int height[6] = {4, 1, 5, 3, 5, 0};
// int finalHeight[10];
// buildWall(n, k, op, left, right, height, finalHeight);
// cout << "finalHeight: ";
// for (auto l: finalHeight) {
// cout << l << ", ";
// }
// cout << endl;
// }
