#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int inf = 100000;
int low[4194304];
int high[4194304];
int l[4194304];
int r[4194304];
int point = 0;
int create(int s, int e){
int now = point++;
if(s==e){
l[now] = -1;
r[now] = -1;
low[now] = 0;
high[now] = 0;
}
else{
int lv = create(s,(s+e)/2);
l[now] = lv;
int rv = create((s+e)/2+1,e);
r[now] = rv;
low[now] = 0;
high[now] = 100000;
}
return now;
}
void push(int now, int nlow, int nhigh){
if(nlow>=high[now]){
high[now] = nlow;
low[now] = nlow;
}
else if(nhigh<=low[now]){
low[now] = nhigh;
high[now] = nhigh;
}
else{
high[now] = min(high[now],nhigh);
low[now] = max(low[now],nlow);
}
}
void upd(int now, int st, int en, int s, int e, int nlow, int nhigh){
if(s==e){
push(now,nlow,nhigh);
return;
}
if(st<=s && e<=en){
push(now,nlow,nhigh);
return;
}
push(l[now],low[now],high[now]);
push(r[now],low[now],high[now]);
low[now] = 0;
high[now] = inf;
if(st<=(s+e)/2){
upd(l[now],st,en,s,(s+e)/2,nlow,nhigh);
}
if(en>(s+e)/2){
upd(r[now],st,en,(s+e)/2+1,e,nlow,nhigh);
}
}
int get(int ind, int now, int s, int e){
if(s==e){
// cout << "@ " << s << " " << e << " " << low[now] << " " << high[now] << endl;
assert(low[now]==high[now]);
return low[now];
}
push(l[now],low[now],high[now]);
push(r[now],low[now],high[now]);
low[now] = 0;
high[now] = inf;
if(ind<=(s+e)/2){
return get(ind,l[now],s,(s+e)/2);
}
else{
return get(ind,r[now],(s+e)/2+1,e);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
// cout << "A " << endl;
int t = create(0,n-1);
// cout << "B " << endl;
for(int i = 0; i<k; i++){
// cout << "C " << i << " " << k << endl;
if(op[i]==1){
//add
// cout << "! " << t << " " << left[i] << " " << right[i] << " " << height[i] << endl;
upd(t,left[i],right[i],0,n-1,height[i],inf);
}
else{
//remove
upd(t,left[i],right[i],0,n-1,0,height[i]);
}
}
// cout << "D " << endl;
for(int i = 0; i<n; i++){
finalHeight[i] = get(i,t,0,n-1);
// cout << "E " << i << " " << finalHeight[i] << endl;
}
}
