#include "wall.h"
#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>
using namespace std;
const int MAXN = 2e6+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
vector<int> niz(MAXN,0);
vector<pair<long long,long long>> seg(MAXN<<2);
vector<long long> maxlazy(MAXN<<2,-inf);
vector<long long> minlazy(MAXN<<2,inf);
void addpush(int nod, int tl, int tr)
{
if(tl == tr)return;
if(maxlazy[nod] == -inf)return;
maxlazy[nod<<1] = max(maxlazy[nod<<1], maxlazy[nod]);
minlazy[nod<<1] = max(minlazy[nod<<1], maxlazy[nod]);
maxlazy[nod<<1|1] = max(maxlazy[nod<<1|1], maxlazy[nod]);
minlazy[nod<<1|1] = max(minlazy[nod<<1|1], maxlazy[nod]);
seg[nod<<1].fi = max(seg[nod<<1].fi, maxlazy[nod]);
seg[nod<<1|1].fi = max(seg[nod<<1|1].fi, maxlazy[nod]);
seg[nod<<1].sc = max(seg[nod<<1].sc, maxlazy[nod]);
seg[nod<<1|1].sc = max(seg[nod<<1|1].sc, maxlazy[nod]);
maxlazy[nod] = -inf;
//minlazy[nod] = inf;
}
void removepush(int nod, int tl, int tr)
{
if(tl == tr)return;
if(minlazy[nod] == inf)return;
maxlazy[nod<<1] = min(maxlazy[nod<<1], minlazy[nod]);
minlazy[nod<<1] = min(minlazy[nod<<1], minlazy[nod]);
maxlazy[nod<<1|1] = min(maxlazy[nod<<1|1], minlazy[nod]);
minlazy[nod<<1|1] = min(minlazy[nod<<1|1], minlazy[nod]);
seg[nod<<1].fi = min(seg[nod<<1].fi, minlazy[nod]);
seg[nod<<1|1].fi = min(seg[nod<<1|1].fi, minlazy[nod]);
seg[nod<<1].sc = min(seg[nod<<1].sc, minlazy[nod]);
seg[nod<<1|1].sc = min(seg[nod<<1|1].sc, minlazy[nod]);
//maxlazy[nod] = -inf;
minlazy[nod] = inf;
}
void push(int nod, int tl, int tr, bool mode)
{
if(mode == 1)
{
removepush(nod, tl, tr);
addpush(nod, tl, tr);
}
else
{
addpush(nod, tl, tr);
removepush(nod, tl, tr);
}
}
void addupdate(int nod, int tl, int tr, int l, int r, int h)
{
if(tl> tr || tl>r || tr<l)return;
if(tl>=l && tr<=r)
{
seg[nod].sc = max(h*1ll, seg[nod].sc);
seg[nod].fi = max(seg[nod].fi, h*1ll);
minlazy[nod] = max(minlazy[nod],h*1ll);
maxlazy[nod] = max(maxlazy[nod],h*1ll);
return;
}
push(nod, tl, tr, 2);
int mid = tl+tr>>1;
addupdate(nod<<1, tl, mid, l ,r, h);
addupdate(nod<<1|1, mid+1, tr, l ,r, h);
seg[nod].fi = max(seg[nod<<1].fi, seg[nod<<1|1].fi);
seg[nod].sc = min(seg[nod<<1].sc, seg[nod<<1|1].sc);
}
void removeupdate(int nod, int tl, int tr, int l, int r, int h)
{
if(tl> tr || tl>r || tr<l)return;
if(tl>=l && tr<=r)
{
seg[nod].sc = min(h*1ll, seg[nod].sc);
seg[nod].fi = min(h*1ll, seg[nod].fi);
minlazy[nod] = min(minlazy[nod],h*1ll);
maxlazy[nod] = min(maxlazy[nod],h*1ll);
return;
}
push(nod, tl, tr, 1);
int mid = tl+tr>>1;
removeupdate(nod<<1, tl, mid, l ,r, h);
removeupdate(nod<<1|1, mid+1, tr, l ,r, h);
seg[nod].fi = max(seg[nod<<1].fi, seg[nod<<1|1].fi);
seg[nod].sc = min(seg[nod<<1].sc, seg[nod<<1|1].sc);
}
int get(int nod, int tl, int tr, int index)
{
push(nod, tl, tr, 1);
if(tl == tr)return seg[nod].sc;
int mid = tl+tr>>1;
if(index<= mid)return get(nod<<1, tl, mid, index);
else return get(nod<<1|1, mid+1, tr, index);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0; i<k; i++)
{
if(op[i] == 1)addupdate(1,1,n,left[i]+1, right[i]+1,height[i]);
else removeupdate(1,1,n,left[i]+1, right[i]+1,height[i]);
}
for(int i=0; i<n; i++)finalHeight[i] = get(1,1,n, i+1);
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
*/
