#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < n; i++)
finalHeight[i] = 0;
if (n <= 10000 && k <= 5000) {
for (int i = 0; i < k; i++) {
for (int j = left[i]; j <= right[i]; j++) {
if (op[i] == 1) finalHeight[j] = max(finalHeight[j], height[i]);
else finalHeight[j] = min(finalHeight[j], height[i]);
}
}
} else {
struct query {
int l, r, h;
};
int sq = sqrt(n);
vector<query> q;
// OPERATION 1
int i = 0;
for (; i < k; i++) {
if (op[i] == 2) break;
q.push_back({left[i], right[i], height[i]});
}
sort(q.begin(), q.end(), [&](query a, query b) {
if (a.l / sq == b.l / sq) return a.r < b.r;
return a.l / sq < b.l / sq;
});
int l = 0, r = 0;
for (auto [vl, vr, vh] : q) {
while (r < vr) {
r++;
finalHeight[r] = max(finalHeight[r], vh);
}
while (l > vl) {
l--;
finalHeight[l] = max(finalHeight[l], vh);
}
while (r > vr) {
r--;
}
while (l < vl) {
l++;
}
}
// OPERATION 2
while (!q.empty()) q.pop_back();
for (; i < k; i++) {
q.push_back({left[i], right[i], height[i]});
}
sort(q.begin(), q.end(), [&](query a, query b) {
if (a.l / sq == b.l / sq) return a.r < b.r;
return a.l / sq < b.l / sq;
});
l = 0, r = 0;
for (auto [vl, vr, vh] : q) {
while (r < vr) {
r++;
finalHeight[r] = min(finalHeight[r], vh);
}
while (l > vl) {
l--;
finalHeight[l] = min(finalHeight[l], vh);
}
while (r > vr) {
r--;
}
while (l < vl) {
l++;
}
}
}
return;
}
