#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#ifdef dremix
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
#define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
#define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
#define p(x)
#define p2(x,y)
#define pp(x)
#define pv(x)
#define ppv(x)
#endif
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 1e18;
const int MOD = 1e9+7;
const int N = 2e5+1;
template<typename T>
struct SEGTREE{
struct node{
T val; // for adding more stuff
T mini,maxi,rep;
node() : val(0), mini(-1), maxi(-1), rep(-1) {}
node(T _val) : val(_val), mini(-1), maxi(-1), rep(-1) {}
};
vector<node> seg;
int N;
void init(int n){
N = n;
seg.assign(4*n,node());
}
node merge(node x, node y){
node res;
return res;
}
void look(node x){
cout<<x.val<<" "<<x.mini<<" "<<x.maxi<<" "<<x.rep<<endl;
}
void add(node &x, int val){
/// if both then max<min
if(x.rep!=-1){
x.rep = max(x.rep,val);
x.val = x.rep;
return;
}
x.maxi = max(x.maxi,val);
if(x.mini !=-1 && x.mini <= x.maxi){
x.rep = x.maxi;
x.mini = -1;
x.maxi = -1;
x.val = x.rep;
}
else{
x.val = max(x.val,x.maxi);
if(x.mini!=-1)
x.val = min(x.val,x.mini);
}
}
void rem(node &x, int val){
/// if both then max < min
if(x.rep!=-1){
x.rep = min(x.rep,val);
x.val = x.rep;
return;
}
if(x.mini == -1)x.mini = val;
else x.mini = min(x.mini,val);
if(x.mini <= x.maxi){
x.rep = x.mini;
x.mini = -1;
x.maxi = -1;
x.val = x.rep;
}
else{
x.val = max(x.val,x.maxi);
x.val = min(x.val,x.mini);
}
}
void push(node &par, node &x, node &y, int r1, int r2){
if(par.rep!=-1){
x.val = par.rep;
x.rep = par.rep;
x.mini = -1;
x.maxi = -1;
y.val = par.rep;
y.rep = par.rep;
y.mini = -1;
y.maxi = -1;
par.rep = -1;
return;
}
if(par.maxi!=-1){
add(x,par.maxi);
add(y,par.maxi);
}
if(par.mini!=-1){
rem(x,par.mini);
rem(y,par.mini);
}
par.maxi = -1;
par.mini = -1;
}
void build(int s, int e, int idx, T arr[]){
if(s == e){
seg[idx] = node(arr[s]);
return;
}
int mid = (s+e)/2;
build(s,mid,idx*2,arr);
build(mid+1,e,idx*2+1,arr);
seg[idx] = merge(seg[idx*2],seg[idx*2+1]);
}
// supports 1-indexing
void build(T arr[]){
build(1,N,1,arr);
}
/// add
void update1(int s, int e, int idx, int qs, int qe, T val){
//cout<<s<<" "<<e<<endl;
//look(seg[idx]);
if(qs<=s && e<=qe){
add(seg[idx],val);
//look(seg[idx]);
return;
}
if(s>qe || e<qs)
return;
int mid = (s+e)/2;
push(seg[idx],seg[idx*2],seg[idx*2+1],mid-s+1,e-mid);
update1(s,mid,idx*2,qs,qe,val);
update1(mid+1,e,idx*2+1,qs,qe,val);
seg[idx] = merge(seg[idx*2],seg[idx*2+1]);
}
// add to all i (l<=i && i<=r) += val
void update1(int l, int r, T val){
update1(1,N,1,l,r,val);
}
/// rem
void update2(int s, int e, int idx, int qs, int qe, T val){
if(qs<=s && e<=qe){
rem(seg[idx],val);
return;
}
if(s>qe || e<qs)
return;
int mid = (s+e)/2;
push(seg[idx],seg[idx*2],seg[idx*2+1],mid-s+1,e-mid);
update2(s,mid,idx*2,qs,qe,val);
update2(mid+1,e,idx*2+1,qs,qe,val);
seg[idx] = merge(seg[idx*2],seg[idx*2+1]);
}
// add to all i (l<=i && i<=r) += val
void update2(int l, int r, T val){
update2(1,N,1,l,r,val);
}
void query(int s, int e, int idx, int ans[]){
if(s==e){
ans[s-1] = seg[idx].val;
return;
}
int mid = (s+e)/2;
push(seg[idx],seg[idx*2],seg[idx*2+1],mid-s+1,e-mid);
query(s,mid,idx*2,ans);
query(mid+1,e,idx*2+1,ans);
}
void query(int ans[]){
query(1,N,1,ans);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SEGTREE<int> seg;
seg.init(n);
int i;
for(i=0;i<k;i++){
//cout<<op[i]<<" "<<left[i]+1<<" "<<right[i]+1<<" "<<height[i]<<endl;
if(op[i]==1){
seg.update1(left[i]+1,right[i]+1,height[i]);
}
else
seg.update2(left[i]+1,right[i]+1,height[i]);
}
seg.query(finalHeight);
}
