#include <iostream>
#include "wall.h"
#define MAXN 2000005
#define MAXH 100000
struct data
{
int low, high;
};
data seg[4*MAXN];
int N;
data add(data x, bool type, int val)
{
if(type)
x.high = std::min(x.high, val);
else
x.low = std::max(x.low, val);
if(x.low >= x.high)
{
if(type)
x.low = x.high;
else
x.high = x.low;
}
return x;
}
void shift(int id)
{
seg[2*id] = add(seg[2*id], 0, seg[id].low);
seg[2*id] = add(seg[2*id], 1, seg[id].high);
seg[2*id+1] = add(seg[2*id+1], 0, seg[id].low);
seg[2*id+1] = add(seg[2*id+1], 1, seg[id].high);
seg[id].low = 0;
seg[id].high = MAXH;
}
void build(int id = 1, int l = 0, int r = N-1)
{
if(l == r)
{
seg[id].low = seg[id].high = 0;
return;
}
seg[id].low = 0;
seg[id].high = MAXH;
int m = (l+r)/2;
build(2*id, l, m);
build(2*id+1, m+1, r);
}
void update(int x, int y, int type, int val, int id = 1, int l = 0, int r = N-1)
{
//std::cout << x << " " << y << " " << type << ' ' << val << " " << id << ' ' << l << ' ' << r << std::endl;
if(y < l || x > r)
return;
if(x <= l && r <= y)
{
seg[id] = add(seg[id], type, val);
//std::cout << seg[id].low << " " << seg[id].high << std::endl;
return;
}
shift(id);
int m = (l+r)/2;
update(x, y, type, val, 2*id, l, m);
update(x, y, type, val, 2*id+1, m+1, r);
}
int val(int x, int id = 1, int l = 0, int r = N-1)
{
if(l == r)
return seg[id].low;
shift(id);
int m = (l+r)/2;
if(x <= m)
return val(x, 2*id, l, m);
else
return val(x, 2*id+1, m+1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
N = n;
build();
for(int i = 0; i < k; i++)
{
update(left[i], right[i], op[i]-1, height[i]);
}
for(int i = 0; i < n; i++)
{
finalHeight[i] = val(i);
}
}
