#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int MAX_N = 2000000;
const int NINF = 0;
const int INF = (1<<30);
struct node {
int first = INF;
int second = NINF;
};
pair<int,int> segt[4*MAX_N+1];
void app(int idx, pair<int,int> a){
segt[idx].second = min(max(segt[idx].second,a.second), a.first);
segt[idx].first = min(max(segt[idx].first,a.second),a.first);
return;
}
void upd(int l, int r, int idx, int tl, int tr, int w, int h){
if (l > tr || r < tl){
return;
}
if (l >= tl && r <= tr){
//mini
if (w == 1){
segt[idx].first = min(segt[idx].first,h);
segt[idx].second = min(segt[idx].second,h);
} else {
segt[idx].first = max(segt[idx].first,h);
segt[idx].second = max(segt[idx].second,h);
}
return;
}
int m = (l+r)/2;
app(2*idx+1,segt[idx]);
app(2*idx+2,segt[idx]);
segt[idx].first = INF;
segt[idx].second = NINF;
upd(l,m,2*idx+1,tl,tr,w,h);
upd(m+1,r,2*idx+2,tl,tr,w,h);
return;
}
void solve(int l, int r, int idx, int finalHeight[]){
if (l == r){
//cout << l << ": " << segt[idx].first << ", " << segt[idx].second << '\n';
if (segt[idx].first == INF && segt[idx].second == NINF){
finalHeight[l] = 0;
} else {
finalHeight[l] = min(segt[idx].first,segt[idx].second);
}
return;
}
int m = (l+r)/2;
app(2*idx+1,segt[idx]);
app(2*idx+2,segt[idx]);
segt[idx].first = INF;
segt[idx].second = NINF;
solve(l,m,2*idx+1,finalHeight);
solve(m+1,r,2*idx+2,finalHeight);
return;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i =0; i < k; i++){
upd(0,n-1,0,left[i],right[i],op[i]-1,height[i]);
}
solve(0,n-1,0,finalHeight);
return;
}
