#include "wall.h"
#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)
using namespace std;
const int lim = 1e5, Nmax = 2e6 + 5;
class SegTree
{
int a[Nmax<<2], b[Nmax<<2];
void combine(int node, int x, int y)
{
if(b[node] <= x) a[node] = b[node] = x;
else if(a[node] >= y) a[node] = b[node] = y;
else a[node] = max(a[node], x), b[node] = min(b[node], y);
}
void propag(int node)
{
combine(left_son, a[node], b[node]);
combine(right_son, a[node], b[node]);
a[node] = 0; b[node] = lim;
}
public:
void update(int node, int st, int dr, int L, int R, int A, int B)
{
if(L <= st && dr <= R)
{
combine(node, A, B);
return;
}
propag(node);
if(L <= mid) update(left_son, st, mid, L, R, A, B);
if(mid < R) update(right_son, mid+1, dr, L, R, A, B);
}
void propag(int node, int st, int dr, int *Ans)
{
if(st == dr)
{
Ans[st] = a[node];
return;
}
propag(node);
propag(left_son, st, mid, Ans);
propag(right_son, mid+1, dr, Ans);
}
void init(int node, int st, int dr)
{
a[node] = 0, b[node] = lim;
if(st == dr) return;
init(left_son, st, mid); init(right_son, mid+1, dr);
}
} aint;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
aint.init(1, 0, n-1);
int i;
for(i=0; i<k; ++i)
aint.update(1, 0, n-1, left[i], right[i], (op[i] == 1 ? height[i] : 0), (op[i] == 1 ? lim : height[i]));
aint.propag(1, 0, n-1, finalHeight);
}
