#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
ll N, K;
vector<ll>ans;
struct segTree
{
ll dd, ht, mid, val, cual ;
bool enEspera;
segTree *L, *R;
segTree(int l, int r){
dd = l;
enEspera = false;
ht = r;
val = 0;
mid = (dd+ht)/2;
if(dd!=ht){
L = new segTree(dd, mid);
R = new segTree(mid+1, ht);
}
}
void propagate(){
L->up(dd, mid, val);
R->up(mid+1, ht, val);
val = 0;
}
void lazy(int cur){
if(dd==ht){
return;
}
if(enEspera){
L->down(dd, mid, cual);
R->down(mid+1, ht, cual);
cual = cur;
if(cual==-1)enEspera=false;
}else{
if(cur==-1)return ;
enEspera=true;
cual = cur;
}
}
void up(int l, int r, ll q){
lazy(-1);
if(l==dd && r == ht){
val = max(q, val);
}else{
propagate();
if(r<=mid){
L->up(l, r, q);
}else if(mid<l){
R->up(l, r, q);
}else{
L->up(l, mid, q);
R->up(mid+1, r, q);
}
}
//if(true)//cout<<dd<< " " << ht<< " - >" << val << endl;
}
void down(int l, int r, ll q){
if(l==dd && r == ht){
if(val==0){
lazy(q);
}else{
val = min(q, val);
}
}else{
propagate();
if(r<=mid){
L->down(l, r, q);
}else if(mid<l){
R->down(l, r, q);
}else{
L->down(l, mid, q);
R->down(mid+1, r, q);
}
}
//cout<<l<< " " << r<< " - >" << val<< endl;
}
void answer(){
lazy(-1);
if(dd==ht){
ans.pb(val);
}else{
propagate();
L->answer();
R->answer();
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
N=n, K=k;
segTree *tri = new segTree(0, n-1);
for(int i = 0 ; i < k ; i ++){
if(op[i]==1){
tri->up(left[i], right[i], height[i]);
}else tri->down(left[i], right[i], height[i]);
}
tri->answer();
for(int i = 0 ; i < n ; i ++)finalHeight[i]=ans[i];
return;
}
