#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,sse4,bmi,bmi2,fma")
using ll = int; using pii = pair<ll,ll>;
const ll Nm = 131072; const ll E = 17;
vector<pii> st; //{min,max}
ll v2(ll x) {
return (__builtin_ctz(x));
}
ll l2(ll x) {
return (31-__builtin_clz(x));
}
pii fz(pii p1, pii p2) {
return {min(p1.first,p2.first),max(p1.second,p2.second)};
}
void pdn(ll p) {
if (p>=Nm) {
return;
}
st[p]=fz(st[2*p],st[2*p+1]);
}
void chmin(ll p, ll nf) {
//cout << "chmin at p,nf="<<p<<","<<nf<<"\n";
if (st[p].first>=nf) {
//cout << "breaking\n";
return;
}
if (p>=Nm) {
//cout << "setting\n";
st[p]={nf,nf};
} else {
chmin(2*p,nf);
chmin(2*p+1,nf);
st[p]=fz(st[2*p],st[2*p+1]);
}
}
void chminI(ll l, ll r, ll nf) {
if (l>r) {
return;
}
ll vl = v2(l); ll vr = v2(r+1);
if (vl<vr) {
chmin((l>>vl)+(1<<(E-vl)),nf);
chminI(l+(1<<vl),r,nf);
} else {
chmin((r>>vr)+(1<<(E-vr)),nf);
chminI(l,r-(1<<vr),nf);
}
}
void chmax(ll p, ll nf) {
//cout << "chmax at p="<<p<<", nf="<<nf<<"\n";
if (st[p].second<=nf) {
//cout << "breaking\n";
return;
}
if (p>=Nm) {
//cout << "setting\n";
st[p]={nf,nf};
} else {
chmax(2*p,nf);
chmax(2*p+1,nf);
st[p]=fz(st[2*p],st[2*p+1]);
}
ll ht = l2(p);
assert(ht>=ht0);
if (ht!=ht0) {
return;
}
p=p/2;
while (p>0) {
st[p]=fz(st[2*p],st[2*p+1]);
p=p/2;
}
}
void chmaxI(ll l, ll r, ll nf) {
//cout << "chmaxI: "<<l<<","<<r<<","<<nf<<"\n";
if (l>r) {
return;
}
ll vl = v2(l); ll vr = v2(r+1);
if (vl<vr) {
chmax((l>>vl)+(1<<(E-vl)),nf);
chmaxI(l+(1<<vl),r,nf);
} else {
chmax((r>>vr)+(1<<(E-vr)),nf);
chmaxI(l,r-(1<<vr),nf);
}
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
st.clear();
for (ll i=0;i<(2*Nm);i++) {
st.push_back({0,0});
}
for (ll k=0;k<K;k++) {
if (op[k]==1) {
chminI(left[k],right[k],height[k]);
} else {
chmaxI(left[k],right[k],height[k]);
}
for (ll e=1;e<=E;e++) {
pdn((l>>e)+(1<<(E-e)));
pdn((r>>e)+(1<<(E-e)));
}
}
for (ll i=0;i<N;i++) {
finalHeight[i]=st[Nm+i].first;
}
}
