#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
// #define cerr if (false) cerr
const int OO = (int)1e18;
struct Segtree {
int height = 0;
int numleaves;
vector<int> nL, nR;
// lo: build
// hi: cut
vector<int> lo, hi;
Segtree (int n) {
numleaves = 1;
while (numleaves < n) numleaves *= 2, height++;
lo.assign(2*numleaves, 0);
hi.assign(2*numleaves, 0);
nL.assign(2*numleaves, 0);
nR.assign(2*numleaves, 0);
for (int i = 0; i < numleaves; i++) {
nL[i + numleaves] = i, nR[i + numleaves] = i;
}
for (int i = numleaves-1; i > 0; i--) {
nL[i] = nL[2*i], nR[i] = nR[2*i+1];
}
}
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 < (int)lo.size()) {
pair<int,int> leftPair = combine(pair<int,int>{lo[node], hi[node]}, pair<int,int>{lo[2*node], hi[2*node]});
lo[2*node] = leftPair.first;
hi[2*node] = leftPair.second;
pair<int,int> rightPair = combine(pair<int,int>{lo[node], hi[node]}, pair<int,int>{lo[2*node+1], hi[2*node+1]});
lo[2*node+1] = rightPair.first;
hi[2*node+1] = rightPair.second;
}
}
int get (int idx) {
int node = 1;
while (node < numleaves) {
pushdown(node);
if (nL[2*node] <= idx && idx <= nR[2*node]) {
node = 2*node;
}
else {
node = 2*node+1;
}
}
return lo[node];
}
void update (int node, int qL, int qR, int newLo, int newHi) {
pushdown(node);
if (qL <= nL[node] && nR[node] <= qR) {
pair<int,int> inter = combine(pair<int,int>{newLo, newHi}, pair<int,int>{lo[node], hi[node]});
lo[node] = inter.first;
hi[node] = inter.second;
pushdown(node);
}
else if (nR[node] < qL || qR < nL[node]) {
return;
}
else {
update(2*node, qL, qR, newLo, newHi);
update(2*node+1, qL, qR, newLo, newHi);
lo[node] = min(lo[2*node], lo[2*node+1]);
hi[node] = max(hi[2*node], hi[2*node+1]);
}
}
void dbg () {
// cerr << "Wall:\n";
// for (int i = 0; i < numleaves; i++) cerr << get(i) << " ";
// cerr << "\n";
cerr << "Tree:\n";
for (int h = 0; h <= height; h++) {
for (int i = (1 << h); i < (1 << (h+1)); i++) {
cerr << "(" << lo[i] << ", " << hi[i] << ") ";
}
cerr << "\n";
}
cerr << "\n";
}
};
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(1, leftQ[q], rightQ[q], heightQ[q], OO);
}
else { // cut
wall.update(1, leftQ[q], rightQ[q], 0, heightQ[q]);
}
// wall.dbg();
}
for (int i = 0; i < N; i++) {
finalHeight[i] = wall.get(i);
}
}
