#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e6+10;
const int inf = 1e12+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];
vector<int> qrsin[maxn], qrsout[maxn];
void build(int no, int l, int r) {
trt[no] = inf;
trb[no] = -inf;
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, int valt, int valb) {
if(l > pos || r < pos) return;
if(l == r) {
trt[no] = valt;
trb[no] = valb;
return;
}
int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
att(f1,l,mid,pos,valt,valb);
att(f2,mid+1,r,pos,valt,valb);
trt[no] = min(trt[f1],trt[f2]);
trb[no] = max(trb[f1],trb[f2]);
}
// find the smallest i such that sfmnt[i] > sfmxb[i]
int findsf(int no, int l, int r, int valt, int valb) {
if(l == r) {
if(min(valt,trt[no]) > max(valb,trb[no])) return l;
else return l+1;
}
int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
if(min(valt,trt[f2]) > max(valb,trb[f2])) return findsf(f1,l,mid,min(valt,trt[f2]),max(valb,trb[f2]));
else return findsf(f2,mid+1,r,valt,valb);
}
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-1);
for(int i = 0; i < n; i++) {
for(auto j : qrsin[i]) {
if(op[j] == 1) att(1,0,k-1,j,height[j],-inf);
if(op[j] == 2) att(1,0,k-1,j,inf,height[j]);
}
finalHeight[i] = height[findsf(1,0,k-1,inf,-inf)];
for(auto j : qrsout[i]) {
if(op[j] == 1) att(1,0,k-1,j,inf,-inf);
if(op[j] == 2) att(1,0,k-1,j,inf,-inf);
}
}
}
