#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
const int MAXN = (int) 2e6 + 5;
typedef pair<int, int> pii;
int * an;
struct node{
int deg = 0;
node * l = NULL;
node * r = NULL;
};
typedef node * pn;
void upd(pn cur, int tl, int tr, int ll, int rr, int dg, int op){
//cerr<<ll<<" "<<rr<<" "<<cur->deg<<endl;
if(ll > rr) return;
if(tl == ll && tr == rr){
if(cur->l == NULL){
if(op == 1){
cur->deg = max(cur->deg, dg);
}else{
cur->deg = min(cur->deg, dg);
}
}else{
assert((cur->r) != NULL);
int tm = (tl + tr) / 2;
upd(cur->l, tl, tm, ll, tm, dg, op);
upd(cur->r, tm + 1, tr, tm + 1, rr, dg, op);
}
}else{
int tm = (tl + tr) / 2;
if(cur->l == NULL){
cur->l = new node;
cur->r = new node;
cur->l->deg = cur->deg;
cur->r->deg = cur->deg;
}
upd(cur->l, tl, tm, ll, min(tm, rr), dg, op);
upd(cur->r, tm + 1, tr, max(ll, tm + 1), rr, dg, op);
}
}
void fina(pn cur, int tl , int tr){
if(cur->l == NULL){
for(int i = tl; i <= tr; i++){
an[i] = cur->deg;
}
}else{
assert(cur->r != NULL);
int tm = (tl + tr) / 2;
fina(cur->l, tl, tm);
fina(cur->r, tm + 1, tr);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
pn root = new node;
root->deg = 0;
an = finalHeight;
for(int i = 0; i < k; i++){
upd(root, 0, n - 1, left[i], right[i], height[i], op[i]);
}
fina(root, 0, n - 1);
return;
}
