#include<bits/stdc++.h>
#include "wall.h"
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=2e6+5;
int N,Q,K,tip[maxn],vis[maxn];
vector<int> poc[maxn],kraj[maxn];
struct slog{
int res=0,minr=1e9;
} st[maxn];
slog spoj(slog a,slog b){
slog ret;
ret.minr=min(a.minr,b.minr);
ret.res=max(b.res,min(a.res,b.minr));
return ret;
}
void update(int gde,slog sta){
gde+=K;
st[gde]=sta;
gde/=2;
while(gde){
st[gde]=spoj(st[gde*2],st[gde*2+1]);
gde/=2;
}
return;
}
void akt(int x){
slog sta;
if(tip[x]==1)
sta.res=vis[x];
else
sta.minr=vis[x];
update(x,sta);
}
void deakt(int x){
slog a;
update(x,a);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
N=n;
Q=k;
K=1;
while(K<Q)
K<<=1;
for(int i=0;i<Q;i++){
poc[left[i]].push_back(i);
kraj[right[i]+1].push_back(i);
tip[i]=op[i];
vis[i]=height[i];
}
for(int i=0;i<N;i++){
for(int x:poc[i])
akt(x);
for(int x:kraj[i])
deakt(x);
finalHeight[i]=st[1].res;
}
}
