#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
class SegmentTree
{
public:
int size;
vector<pair<int,int>> a;
vector<pair<bool,int>> lazy;
// pair item 1 : low operation
// pair item 2 : high operation
SegmentTree(int s)
{
size = s;
for (int i = 0; i < (4*size)+1; i++)
{
a.push_back({0,0});
lazy.push_back({0,-1});
// lazy item 1 = operation type
// lazy item 2 = k
}
}
void update(int v, int coveredStart, int coveredEnd, int l, int r, bool op, int k)
{
/*V = current vertex | coveredStart = start of range covered by current vertex |
coveredEnd = end of range covered by current vertex | l = left of query
r = right of query | op = operation type [add/remove] | k = X for operation*/
// node lies entirely outside of desired range
if (r < coveredStart || l > coveredEnd)
{
return;
}
// node lies entirely within desired range
else if (coveredStart >= l && coveredEnd <= r)
{
if (op==0)
{
// ADD operation
a[v].first=max(a[v].first,k);
a[v].second=max(a[v].second,k);
}
else{
// REMOVE operation
a[v].first=min(a[v].first,k);
a[v].second=min(a[v].second,k);
}
if (coveredStart != coveredEnd)
{
lazy[v]={op,k};
}
}
// node lies partially within desired range
else{
int mid = (coveredStart+coveredEnd)/2;
if (lazy[v].second!=-1)
{
// propagate change downwards
update(v*2,coveredStart,mid,coveredStart,mid,lazy[v].first,lazy[v].second);
update((v*2)+1,mid+1,coveredEnd,mid+1,coveredEnd,lazy[v].first,lazy[v].second);
lazy[v].second=-1;
}
// left child
update(v*2,coveredStart,mid,l,r,op,k);
// right child
update((v*2)+1,mid+1,coveredEnd,l,r,op,k);
// update parent node range
a[v].first=min(a[v*2].first,a[(v*2)+1].first);
a[v].second=max(a[v*2].second,a[(v*2)+1].second);
}
}
int traverse(int v, int l, int r, int target)
{
// base case -> target found
if (l==r && l == target)
{
return a[v].first;
}
// out of range
else if (l > target || r < target)
{
return -1;
}
// partially in range
else{
int mid = (l+r)/2;
if (lazy[v].second != -1)
{
update(v*2,l,mid,l,mid,lazy[v].first,lazy[v].second);
update((v*2)+1,mid+1,r,mid+1,r,lazy[v].first,lazy[v].second);
lazy[v].second=-1;
}
int left = traverse(v*2,l,mid,target);
int right = traverse((v*2)+1,mid+1,r,target);
return max(left,right);
}
}
};
void buildWall(int n, int k, int op[], int left[],int right[], int height[], int finalHeight[])
{
SegmentTree segTree = SegmentTree(n);
for (int i = 0; i < k; i++)
{
int l = left[i];
int r = right[i];
int operation = op[i]-1;
int h = height[i];
segTree.update(1,0,n-1,l,r,operation,h);
}
for (int i = 0; i < k; i++)
{
finalHeight[i] = segTree.traverse(1,0,n-1,i);
}
}
