#include "wall.h"
#define N 2000001
#define max2(x,y) (x>y?x:y)
#define min2(x,y) (x<y?x:y)
struct WALL{
int op, h;
} Tree[N * 4][2], NONO;
int n, nn, m;
WALL make_WALL(int op, int h)
{
WALL temp;
temp.op = op, temp.h = h;
return temp;
}
void g(int lev, WALL num)
{
if (num.op == -1) return;
if (Tree[lev][0].op == -1){ Tree[lev][0] = num; return; }
if (Tree[lev][1].op == -1){ Tree[lev][1] = num; return; }
if (Tree[lev][0].op == Tree[lev][1].op)
{
if (Tree[lev][0].op == 1) Tree[lev][0].h = max2(Tree[lev][0].h, Tree[lev][1].h);
else Tree[lev][0].h = min2(Tree[lev][0].h, Tree[lev][1].h);
Tree[lev][1] = num; return;
}
if (Tree[lev][1].op == num.op)
{
if (num.op == 1) Tree[lev][1].h = max2(Tree[lev][1].h, num.h);
else Tree[lev][1].h = min2(Tree[lev][1].h, num.h);
return;
}
if (Tree[lev][1].op == 1)
{
if (Tree[lev][1].h > Tree[lev][0].h)
{
if (num.h < Tree[lev][1].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
return;
}
if (num.h < Tree[lev][0].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
}
else
{
if (Tree[lev][0].h>Tree[lev][1].h)
{
if (num.h>Tree[lev][1].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
return;
}
if (num.h > Tree[lev][0].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
}
}
void Push(int lev, int l, int r, int x, int y, WALL num)
{
int mid = (l + r) / 2;
if (r < x || y < l) return;
if (x <= l && r <= y){ g(lev, num); return; }
g(lev * 2, Tree[lev][0]), g(lev * 2, Tree[lev][1]);
g(lev * 2 + 1, Tree[lev][0]), g(lev * 2 + 1, Tree[lev][1]);
Tree[lev][0] = Tree[lev][1] = NONO;
Push(lev * 2, l, mid, x, y, num), Push(lev * 2 + 1, mid + 1, r, x, y, num);
}
int get_h(int lev, int h)
{
if (lev == 0) return h;
if (Tree[lev][0].op == 1) h = max2(h, Tree[lev][0].h);
if (Tree[lev][0].op == 2) h = min2(h, Tree[lev][0].h);
if (Tree[lev][1].op == 1) h = max2(h, Tree[lev][1].h);
if (Tree[lev][1].op == 2) h = min2(h, Tree[lev][1].h);
return get_h(lev / 2, h);
}
void buildWall(int _n, int _m, int _in1[], int _in2[], int _in3[], int _in4[], int out[]){
WALL temp;
int x, y;
n=_n, m=_m, NONO = make_WALL(-1, -1);
for (nn = 1; nn < n; nn *= 2);
for (int i = 1; i < nn * 2; i++) Tree[i][0] = Tree[i][1] = NONO;
for (int i = 1; i <= m; i++){
temp.op=_in1[i-1], x=_in2[i-1], y=_in3[i-1], temp.h=_in4[i-1];
x++, y++, Push(1, 1, nn, x, y, temp);
}
for (int i = 1; i <= n; i++) out[i-1]=get_h(nn + i - 1, 0);
}
