#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;
const int maxv = 1<<30;
struct seg{
seg *r, *l;
int lb, rb;
bool ch;
int mxval, mnval;
int mid;
seg () : l(NULL), r(NULL), ch(false), mnval(0), mxval(maxv) {}
void init(int lx, int rx){
lb = lx, rb = rx;
mid = (lx+rx)>>1;
}
void ex(){
if(r == NULL){
r = new seg;
r->init(mid+1,rb);
}
if(l == NULL){
l = new seg;
l->init(lb,mid);
}
}
void push(){
r->mxval = min(r->mxval,mxval);
r->mnval = min(r->mnval,r->mxval);
r->mnval = max(r->mnval,mnval);
r->mxval = max(r->mxval,r->mnval);
r->ch = true;
l->mxval = min(l->mxval,mxval);
l->mnval = min(l->mnval,l->mxval);
l->mnval = max(l->mnval,mnval);
l->mxval = max(l->mxval,l->mnval);
l->ch = true;
mnval = 0;
mxval = maxv;
ch = false;
}
void add(int cl, int cr, int am){
if(lb > cr || rb < cl)return;
if(lb >= cl && rb <= cr){
mnval = max(mnval,am);
mxval = max(mxval,mnval);
ch = true;
return;
}
ex();
if(ch)push();
l->add(cl,cr,am);
r->add(cl,cr,am);
}
void rem(int cl, int cr, int am){
if(lb > cr || rb < cl)return;
if(lb >= cl && rb <= cr){
mxval = min(mxval,am);
mnval = min(mnval,mxval);
ch = true;
return;
}
ex();
if(ch)push();
l->rem(cl,cr,am);
r->rem(cl,cr,am);
}
int fin(int x){
if(lb == rb){
return mnval;
}
ex();
if(ch)push();
if(x > mid)return r->fin(x);
return l->fin(x);
}
};
seg *root = new seg;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
root->init(0,n-1);
for(int i = 0; i < k; ++i){
if(op[i] == 1){
root->add(left[i],right[i],height[i]);
}
else{
root->rem(left[i],right[i],height[i]);
}
}
for(int i = 0; i < n; ++i){
finalHeight[i] = root->fin(i);
}
return;
}
