#include "wall.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <bitset>
int lowSeg[8000010] = { 0 }, highSeg[8000010] = { 0 };
int ans[2000010] = { 0 };
void construct(int low, int high, int pos)
{
if (low == high)
{
lowSeg[pos] = 0;
highSeg[pos] = 0;
return;
}
lowSeg[pos] = 1e6;
highSeg[pos] = -1;
int mid = low + (high - low) / 2;
construct(low, mid, pos * 2 + 1);
construct(mid + 1, high, pos * 2 + 2);
}
void update(int low, int high, int qlow, int qhigh, int value, int oper, int pos)
{
if (low > qhigh || high < qlow)
return;
if (qlow <= low && high <= qhigh)
{
if (oper == 2)
{
lowSeg[pos] = std::min(lowSeg[pos], value);
}
else
{
highSeg[pos] = std::max(highSeg[pos], value);
}
if (lowSeg[pos] < highSeg[pos])
{
lowSeg[pos] = value;
highSeg[pos] = value;
}
int next1 = pos * 2 + 1;
int next2 = pos * 2 + 2;
if (low != high)
{
if (lowSeg[pos] <= highSeg[next1])
{
lowSeg[next1] = lowSeg[pos];
highSeg[next1] = lowSeg[pos];
}
else if (highSeg[pos] >= lowSeg[next1])
{
lowSeg[next1] = highSeg[pos];
highSeg[next1] = highSeg[pos];
}
else
{
lowSeg[next1] = std::min(lowSeg[next1], lowSeg[pos]);
highSeg[next1] = std::max(highSeg[next1], highSeg[pos]);
}
if (lowSeg[pos] <= highSeg[next2])
{
lowSeg[next2] = lowSeg[pos];
highSeg[next2] = lowSeg[pos];
}
else if (highSeg[pos] >= lowSeg[next2])
{
lowSeg[next2] = highSeg[pos];
highSeg[next2] = highSeg[pos];
}
else
{
lowSeg[next2] = std::min(lowSeg[next2], lowSeg[pos]);
highSeg[next2] = std::max(highSeg[next2], highSeg[pos]);
}
lowSeg[pos] = 1e6;
highSeg[pos] = -1;
}
return;
}
int next1 = pos * 2 + 1;
int next2 = pos * 2 + 2;
if (lowSeg[pos] <= highSeg[next1])
{
lowSeg[next1] = lowSeg[pos];
highSeg[next1] = lowSeg[pos];
}
else if (highSeg[pos] >= lowSeg[next1])
{
lowSeg[next1] = highSeg[pos];
highSeg[next1] = highSeg[pos];
}
else
{
lowSeg[next1] = std::min(lowSeg[next1], lowSeg[pos]);
highSeg[next1] = std::max(highSeg[next1], highSeg[pos]);
}
if (lowSeg[pos] <= highSeg[next2])
{
lowSeg[next2] = lowSeg[pos];
highSeg[next2] = lowSeg[pos];
}
else if (highSeg[pos] >= lowSeg[next2])
{
lowSeg[next2] = highSeg[pos];
highSeg[next2] = highSeg[pos];
}
else
{
lowSeg[next2] = std::min(lowSeg[next2], lowSeg[pos]);
highSeg[next2] = std::max(highSeg[next2], highSeg[pos]);
}
lowSeg[pos] = 1e6;
highSeg[pos] = -1;
int mid = low + (high - low) / 2;
update(low, mid, qlow, qhigh, value, oper, next1);
update(mid + 1, high, qlow, qhigh, value, oper, next2);
}
void spread(int low, int high, int pos)
{
if (low == high)
{
ans[low] = lowSeg[pos];
return;
}
int next1 = pos * 2 + 1;
int next2 = pos * 2 + 2;
if (lowSeg[pos] <= highSeg[next1])
{
lowSeg[next1] = lowSeg[pos];
highSeg[next1] = lowSeg[pos];
}
else if (highSeg[pos] >= lowSeg[next1])
{
lowSeg[next1] = highSeg[pos];
highSeg[next1] = highSeg[pos];
}
else
{
lowSeg[next1] = std::min(lowSeg[next1], lowSeg[pos]);
highSeg[next1] = std::max(highSeg[next1], highSeg[pos]);
}
if (lowSeg[pos] <= highSeg[next2])
{
lowSeg[next2] = lowSeg[pos];
highSeg[next2] = lowSeg[pos];
}
else if (highSeg[pos] >= lowSeg[next2])
{
lowSeg[next2] = highSeg[pos];
highSeg[next2] = highSeg[pos];
}
else
{
lowSeg[next2] = std::min(lowSeg[next2], lowSeg[pos]);
highSeg[next2] = std::max(highSeg[next2], highSeg[pos]);
}
int mid = low + (high - low) / 2;
spread(low, mid, next1);
spread(mid + 1, high, next2);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
construct(0, n - 1, 0);
for (int i = 0; i < k; ++i)
{
update(0, n - 1, left[i], right[i], height[i], op[i], 0);
}
spread(0, n - 1, 0);
for (int i = 0; i < n; ++i)
{
finalHeight[i] = ans[i];
}
}
