#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, LIM = 1e5 + 5;
vector<int> add[4 * N], rem[4 * N];
struct segtreemin{
int seg[4 * N];
void build(int nd, int l, int r){
if(l == r) return seg[nd] = LIM, void();
int md = (l + r) / 2;
build(nd * 2, l, md);
build(nd * 2 + 1, md + 1, r);
seg[nd] = min(seg[nd * 2], seg[nd * 2 + 1]);
}
void upd(int nd, int l, int r, int pos, int v){
if(l == r) return seg[nd] = v, void();
int md = (l + r) / 2;
if(pos <= md) upd(nd * 2, l, md, pos, v);
else upd(nd * 2 + 1, md + 1, r, pos, v);
seg[nd] = min(seg[nd * 2], seg[nd * 2 + 1]);
}
int qry(int nd, int l, int r, int x){
if(seg[nd] >= x) return -1;
if(l == r) return l;
int md = (l + r) / 2;
if(seg[nd * 2 + 1] < x) return qry(nd * 2 + 1, md + 1, r, x);
return qry(nd * 2, l, md, x);
}
}trem;
struct segtreemax{
int seg[4 * N];
void build(int nd, int l, int r){
if(l == r) return seg[nd] = -LIM, void();
int md = (l + r) / 2;
build(nd * 2, l, md);
build(nd * 2 + 1, md + 1, r);
seg[nd] = max(seg[nd * 2], seg[nd * 2 + 1]);
}
void upd(int nd, int l, int r, int pos, int v){
if(l == r) return seg[nd] = v, void();
int md = (l + r) / 2;
if(pos <= md) upd(nd * 2, l, md, pos, v);
else upd(nd * 2 + 1, md + 1, r, pos, v);
seg[nd] = max(seg[nd * 2], seg[nd * 2 + 1]);
}
int qry(int nd, int l, int r, int x){
if(seg[nd] < x) return -1;
if(l == r) return l;
int md = (l + r) / 2;
if(seg[nd * 2 + 1] >= x) return qry(nd * 2 + 1, md + 1, r, x);
return qry(nd * 2, l, md, x);
}
}tadd;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 0;i<k;i++){
add[left[i] + 1].push_back(i);
rem[right[i] + 1].push_back(i);
}
tadd.build(1, 1, k);
trem.build(1, 1, k);
for(int i = 1;i<=n;i++){
for(auto x : add[i]){
if(op[x] == 1) tadd.upd(1, 1, k, x + 1, height[x]);
else trem.upd(1, 1, k, x + 1, height[x]);
}
int l = 1, r = 100000, res = 0;
while(l <= r){
int md = (l + r) / 2;
int id1 = tadd.qry(1, 1, k, md), id2 = trem.qry(1, 1, k, md);
if(id1 > id2){
res = md;
l = md + 1;
}else{
r = md - 1;
}
}
finalHeight[i - 1] = res;
for(auto x : rem[i]){
if(op[x] == 1) tadd.upd(1, 1, k, x + 1, -LIM);
else trem.upd(1, 1, k, x + 1, LIM);
}
}
}
