#include "wall.h"
#include <vector>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 100000;
int const inf = 1000000000;
struct Node{
int from;
int to;
Node(int from = 0, int to = inf){
this->from = from;
this->to = to;
}
Node operator + (Node const &a) const{
Node result;
if(a.to <= from)
return {from, from};
else if(to <= a.from)
return {to, to};
else
return {MAX(from, a.from), MIN(to, a.to)};
}
};
class SegmentTree{
private:
std::vector<Node> aint;
public:
SegmentTree(int n){
aint.resize(4 * n);
}
void cleannode(int node, int from, int to){
if(from < to){
int mid = (from + to) / 2;
aint[node * 2] = aint[node] + aint[node * 2];
aint[node * 2 + 1] = aint[node] + aint[node * 2 + 1];
aint[node] = {0, inf};
}
}
void build(int node, int from, int to){
if(from < to){
int mid = (from + to) / 2;
build(node * 2, from, mid);
build(node * 2 + 1, mid + 1, to);
} else
aint[node] = {0, 0};
}
void update(int node, int from, int to, int x, int y, Node val){
cleannode(node, from, to);
if(from == x && to == y)
aint[node] = val + aint[node];
else {
int mid = (from + to) / 2;
if(x <= mid)
update(node * 2, from, mid, x, MIN(mid, y), val);
if(mid + 1 <= y)
update(node * 2 + 1, mid + 1, to, MAX(mid + 1, x), y, val);
}
}
Node query(int node, int from, int to, int x){
cleannode(node, from, to);
if(from < to){
int mid = (from + to) / 2;
if(x <= mid)
return query(node * 2, from, mid, x);
else
return query(node * 2 + 1, mid + 1, to, x);
} else
return aint[node];
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SegmentTree aint(n);
aint.build(1, 0, n - 1);
for(int i = 0; i < k; i++)
if(op[i] == 1)
aint.update(1, 0, n - 1, left[i], right[i], {height[i], inf});
else
aint.update(1, 0, n - 1, left[i], right[i], {0, height[i]});
for(int i = 0; i < n; i++)
finalHeight[i] = aint.query(1, 0, n - 1, i).from;
return;
}
/*
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
*/
