#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
#define pb push_back
const int maxk = 5e5+10;
const int maxn = 2e6+10;
const int inf = 1e9+10;
int tra[4*maxk], trb[4*maxk];
vector<int> adds[maxn], rems[maxn];
void build(int no, int l, int r) {
tra[no] = -inf;
trb[no] = inf;
if(l == r) return;
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
void upd(int no, int l, int r, int pos, int newa, int newb) {
if(l > pos || r < pos) return;
if(l == r) {
if(newa != -1) tra[no] = newa;
if(newb != -1) trb[no] = newb;
return;
}
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
upd(lc,l,mid,pos,newa,newb);
upd(rc,mid+1,r,pos,newa,newb);
tra[no] = max(tra[lc],tra[rc]);
trb[no] = min(trb[lc],trb[rc]);
}
pair<int,pair<int,int>> find(int no, int l, int r, int maxa, int minb) {
if(l == r) return mp(l+1,mp(maxa,minb));
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
if(max(maxa,tra[rc]) < min(minb,trb[rc])) return find(lc,l,mid,max(maxa,tra[rc]),min(minb,trb[rc]));
else return find(rc,mid+1,r,maxa,minb);
}
void buildWall(int n, int k, int op[], int lf[], int rg[], int h[], int finalHeight[]){
for(int i = 0; i < k; i++) {
adds[lf[i]].pb(i);
rems[rg[i]].pb(i);
}
build(1,0,k);
for(int i = 0; i < n; i++) {
for(auto j : adds[i]) {
if(op[j] == 1) {
upd(1,0,k,j+1,h[j],-1);
}
else {
upd(1,0,k,j+1,-1,h[j]);
}
}
upd(1,0,k,0,0,0);
auto aux = find(1,0,k,-inf,inf);
int hcur;
if(aux.fr-1 == 0) hcur = 0;
else hcur = h[aux.fr-2];
int maxa = aux.sc.fr;
int minb = aux.sc.sc;
hcur = min(hcur,minb);
hcur = max(hcur,maxa);
finalHeight[i] = hcur;
for(auto j : rems[i]) {
if(op[j] == 1) {
upd(1,0,k,j+1,-inf,-1);
}
else {
upd(1,0,k,j+1,-1,inf);
}
}
}
}
