#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e6+10;
const int inf = 1e9+10;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
int n, trt[4*maxn], trb[4*maxn];
pair<int,int> trmnb[4*maxn], trmxt[4*maxn];
vector<int> qrsin[maxn], qrsout[maxn];
void build(int no, int l, int r) {
trt[no] = inf;
trb[no] = -inf;
trmxt[no] = mp(-inf,-1);
trmnb[no] = mp(inf,-1);
if(l == r) return;
int f1=2*no,f2=2*no+1,mid=(l+r)/2;
build(f1,l,mid);
build(f2,mid+1,r);
}
void att(int no, int l, int r, int pos, pair<int,int> mxt, pair<int,int> mnb) {
if(l > pos || r < pos) return;
if(l == r) {
trmxt[no] = mxt;
trmnb[no] = mnb;
return;
}
int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
att(f1,l,mid,pos,mxt,mnb);
att(f2,mid+1,r,pos,mxt,mnb);
trmxt[no] = max(trmxt[f1],trmxt[f2]);
trmnb[no] = min(trmnb[f1],trmnb[f2]);
}
// find the smallest i such that sfmnt[i] > sfmxb[i]
pair<pair<int,int>,pair<int,int>> findsf(int no, int l, int r, pair<int,int> mxt, pair<int,int> mnb) {
if(l == r) {
// cout << l << " - " << r << " " << valt << " , " << trt[no] << " " << valb << " , " << trb[no] << endl;
// if(max(mxt,trmxt[no]) <= min(mnb,trmnb[no])) return l;
// else return l+1;
if(max(mxt,trmxt[no]) <= min(mnb,trmnb[no])) return mp(max(mxt,trmxt[no]),min(mnb,trmnb[no]));
else return mp(mxt,mnb);
}
int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
if(max(mxt,trmxt[f2]) <= min(mnb,trmnb[f2])) return findsf(f1,l,mid,max(mxt,trmxt[f2]), min(mnb,trmnb[f2]));
else return findsf(f2,mid+1,r,mxt,mnb);
}
void buildWall(int32_t N, int32_t k, int32_t op[], int32_t left[], int32_t right[], int32_t height[], int32_t finalHeight[]){
n = N;
for(int i = 0; i < k; i++) {
qrsin[left[i]].pb(i);
qrsout[right[i]].pb(i);
}
build(1,0,k);
set<int> st;
att(1,0,k,0,mp(0,0),mp(inf,-1));
for(int i = 0; i < n; i++) {
for(auto j : qrsin[i]) {
st.insert(j);
// cout << " " << j << endl;
if(op[j] == 1) att(1,0,k,j+1,mp(height[j],j),mp(inf,-1));
if(op[j] == 2) att(1,0,k,j+1,mp(-inf,-1),mp(height[j],j));
}
auto aux = findsf(1,0,k-1,mp(-inf,-1),mp(inf,-1));
auto mxt = aux.fr;
auto mnb = aux.sc;
if(mxt.sc == -1) finalHeight[i] = mnb.fr;
else if(mnb.sc == -1) finalHeight[i] = mxt.fr;
else if(mxt.sc < mnb.sc) finalHeight[i] = mxt.fr;
else finalHeight[i] = mnb.fr;
// finalHeight[i] = height[*st.lower_bound(x)];
for(auto j : qrsout[i]) {
st.erase(j);
if(op[j] == 1) att(1,0,k,j+1,mp(-inf,-1),mp(inf,-1));
if(op[j] == 2) att(1,0,k,j+1,mp(-inf,-1),mp(inf,-1));
}
}
}
