#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
// define
#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define ll long long
#define ld double
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) (((x)>>(i))&1LL)
#define flip(x,i) ((x)^(1LL<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define sitingfake 1
#define orz 1
//constant
const ll mod = 1e9 + 7;
const long long linf = 4557430888798830399;
const int inf = 1061109567;
const int maxarr = 1e6 + 5;
const int dx[] = {0,1,-1,0};
const int dy[] = {1,0,0,-1};
template<typename T> bool maximize(T &a, const T &b)
{
if(a < b) {a = b; return 1;}
return 0;
}
template<typename T> bool minimize(T &a, const T &b)
{
if(a > b) {a = b; return 1;}
return 0;
}
inline void Plus(ll & a ,ll b)
{
b %= mod;
a += b;
if(a >= mod) a -= mod;
if(a < 0) a += mod;
return;
}
inline void Mul(ll & a, ll b)
{
a %= mod; b %= mod;
a *= b;
a %= mod;
return;
}
//code
//
//const int maxn = 1e5 + 7;
//
//int op[maxn] , Left[maxn] , Right[maxn] , finalHeight[maxn] , height[maxn];
//int n , k;
struct SegTree
{
struct Node
{
int Max1;
int Max2;
int Min1;
int Min2;
Node ()
{
Max1 = inf;
Max2 = -inf;
Min1 = 0;
Min2 = inf;
}
Node operator + (Node & other)
{
Node ans;
if(Max1 == other.Max1)
{
ans.Max1 = Max1;
ans.Max2 = max(Max2 , other.Max2);
}
else if(Max1 > other.Max1)
{
ans.Max1 = Max1;
ans.Max2 = max(Max2 , other.Max1);
}
else
{
ans.Max1 = other.Max1;
ans.Max2 = max(Max1 , other.Max2);
}
if(Min1 == other.Min1)
{
ans.Min1 = Min1;
ans.Min2 = min(Min2 , other.Min2);
}
else if(Min1 < other.Min1)
{
ans.Min1 = Min1;
ans.Min2 = min(Min2 , other.Min1);
}
else
{
ans.Min1 = other.Min1;
ans.Min2 = min(Min1 , other.Min2);
}
return ans;
}
};
vector <Node> st;
SegTree(int n)
{
st.resize(4 * (n + 2));
}
void Build(int i ,int l ,int r)
{
if(l == r)
{
st[i].Max1 = st[i].Min1 = 0;
return;
}
int mid = (r + l) >> 1;
Build(i * 2 , l , mid);
Build(i * 2 + 1, mid + 1, r);
st[i] = st[i * 2] + st[i * 2 + 1];
}
inline void ApplyMax(int i , int val)
{
if(st[i].Min1 >= val) return;
st[i].Min1 = val;
if(st[i].Max2 == -inf)
{
st[i].Max1 = val;
return;
}
if(st[i].Min1 >= st[i].Max1)
{
st[i].Max1 = val;
}
else if(st[i].Min1 > st[i].Max2)
{
st[i].Max2 = val;
}
}
inline void ApplyMin(int i ,int val)
{
if(st[i].Max1 <= val) return;
st[i].Max1 = val;
if(st[i].Min2 == inf)
{
st[i].Min1 = val;
return;
}
if(st[i].Max1 <= st[i].Min1)
{
st[i].Min1 = val;
}
else if(st[i].Max1 < st[i].Min2)
{
st[i].Min2 = val;
}
}
inline void Push(int i)
{
ApplyMax(i * 2 , st[i].Min1);
ApplyMax(i * 2 + 1, st[i].Min1);
ApplyMin(i * 2 , st[i].Max1);
ApplyMin(i * 2 + 1, st[i].Max1);
}
void UpdateMax(int i ,int l ,int r , int u , int v , int val)
{
if(u > r || v < l || st[i].Min1 >= val) return;
if(u <= l && r <= v && st[i].Min2 > val)
{
ApplyMax(i , val);
return;
}
int mid = (r + l) >> 1;
Push(i);
UpdateMax(i * 2 ,l , mid , u , v , val);
UpdateMax(i * 2 + 1, mid + 1, r, u , v, val);
st[i] = st[i * 2] + st[i * 2 + 1];
}
void UpdateMin(int i ,int l ,int r ,int u, int v , int val)
{
if(u > r || v < l || st[i].Max1 <= val) return;
if(u <= l && r <= v && st[i].Max2 < val)
{
ApplyMin(i , val);
return;
}
int mid = (r + l) >> 1;
Push(i);
UpdateMin(i * 2 ,l , mid , u , v , val);
UpdateMin(i * 2 + 1, mid + 1, r, u , v, val);
st[i] = st[i * 2] + st[i * 2 + 1];
}
int getPos(int i , int l ,int r, int pos)
{
if(pos > r || pos < l) return 0;
if(l == r) return st[i].Max1;
int mid = (r + l) >> 1;
Push(i);
if(pos <= mid) return getPos(i * 2 , l , mid , pos);
return getPos(i * 2 + 1 , mid + 1, r, pos);
}
};
void buildWall(int n , int k , int op[] , int Left[] , int Right[] , int height[] , int finalHeight[])
{
SegTree st(n);
st.Build(1 ,0 , n - 1);
for(int i = 0 ; i < k ; i++)
{
if(op[i] == 1)
{
st.UpdateMax(1 , 0 , n - 1 , Left[i] , Right[i] , height[i]);
}
else
{
st.UpdateMin(1 , 0 , n - 1 , Left[i] , Right[i] , height[i]);
}
}
for(int i = 0; i < n ; i++)
{
finalHeight[i] = st.getPos(1 , 0 , n - 1 , i);
}
}
//signed main()
//{
// ios_base :: sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
//
// cin >> n >> k;
//
// for(int i = 0; i < k ; i++)
// {
// cin >> op[i] >> Left[i] >> Right[i] >> height[i];
// }
//
// buildWall(n , k , op , Left , Right , height , finalHeight);
//
// for(int i = 0; i < n ;i++)
// {
// cout << finalHeight[i] << '\n';
// }
//
//}
