#pragma once
#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<int,int>
const int mxN = (1 << 22);
const int mod = 1e9 + 7;
const int inf = INT_MAX;
using namespace std;
struct event{
int ty,op,id,val;
};
vector<event>q[mxN];
pii seg[mxN];
int N,s,e;
pii combine(pii a,pii b){
pii c = a;
c.F = min(c.F,b.S);
c.F = max(c.F,b.F);
c.S = min(a.S,b.S);
return c;
}
void update(int ind,pii val){
ind += N;
seg[ind] = val;
while(ind /= 2) seg[ind] = combine(seg[ind * 2],seg[ind * 2 + 1]);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
// N = exp2(ceil(log2(n)));
N = 1 << 20;
for(int i = 1;i < N * 2;i++){
seg[i] = {0,inf};
}
for(int i = 0;i < k;i++){
q[left[i]].push_back({1,op[i],i,height[i]});
q[right[i] + 1].push_back({-1,op[i],i,height[i]});
}
for(int i = 0;i < n;i++){
while(q[i].size()){
auto u = q[i].back();
q[i].pop_back();
if(u.ty == -1){
update(u.id,{0,inf});
}else{
if(u.op == 1) update(u.id,{u.val,inf});
else update(u.id, {0,u.val});
}
}
finalHeight[i] = seg[1].F;
}
}
