#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back
void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}
template<typename T,typename V>
void PRINT(pair<T,V>& x){
cerr<<"{";
PRINT(x.fi);
cerr<<",";
PRINT(x.se);
cerr<<"}";
}
template<typename T>
void PRINT(T &x){
int id=0;
cerr<<"{";
for(auto _i:x){
cerr<<(id++ ? "," : "");
PRINT(_i);
}
cerr<<"}";
}
void _PRINT(){
cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
PRINT(h);
if(sizeof...(t)) cerr<<", ";
_PRINT(t...);
}
#define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x)
vector<pii> seg;
pii Merge(pii p,pii q){
if(p.fi<=q.fi && q.fi<=p.se) p.fi=q.fi;
else if(q.fi>p.se){
p.fi=q.fi;
p.se=q.fi;
}
if(p.fi<=q.se && q.se<=p.se) p.se=q.se;
else if(q.se<p.fi){
p.fi=q.se;
p.se=q.se;
}
return p;
}
void Propagate(int node,int l,int r){
if(l!=r){
seg[2*node]=Merge(seg[2*node],seg[node]);
seg[2*node+1]=Merge(seg[2*node+1],seg[node]);
seg[node]={0,INF};
}
}
void UpdateR(int node,int l,int r,int L,int R,int x){
Propagate(node,l,r);
if(L<=l && r<=R){
seg[node]=Merge(seg[node],{0,x});
return;
}
if(L<=mid) UpdateR(2*node,l,mid,L,R,x);
if(R>mid) UpdateR(2*node+1,mid+1,r,L,R,x);
}
void UpdateL(int node,int l,int r,int L,int R,int x){
Propagate(node,l,r);
if(L<=l && r<=R){
seg[node]=Merge(seg[node],{x,INF});
return;
}
if(L<=mid) UpdateL(2*node,l,mid,L,R,x);
if(R>mid) UpdateL(2*node+1,mid+1,r,L,R,x);
}
pii Query(int node,int l,int r,int idx){
if(l==r){
return seg[node];
}
pii q;
if(idx<=mid) q=Query(2*node,l,mid,idx);
else q=Query(2*node+1,mid+1,r,idx);
return Merge(q,seg[node]);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
seg.resize(4*n+1,{0,INF});
for(int i=0;i<k;i++){
int tp=op[i];
int l=left[i];
int r=right[i];
int x=height[i];
if(tp==1) UpdateL(1,0,n-1,l,r,x);
else UpdateR(1,0,n-1,l,r,x);
}
for(int i=0;i<n;i++){
pii q=Query(1,0,n-1,i);
finalHeight[i]=q.fi;
}
return;
}
/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/
