#include "wall.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 2e6 + 5;
int mx[maxn * 4] , mn[maxn * 4];
int lz[maxn * 4];
void push(int x , bool key){
if(lz[x] != -1){
mx[x] = mn[x] = lz[x];
if(key)lz[x * 2] = lz[x * 2 + 1] = lz[x];
}
lz[x] = -1;
}
void upMin(int x , int l , int r , int L , int R , int val){
push(x , l != r);
if(l > R || L > r || mx[x] <= val)return;
if(L <= l && r <= R && mn[x] >= val){
lz[x] = val;push(x , l != r);
return;
}
int mid = l + r >> 1;
upMin(x * 2, l , mid , L , R , val);
upMin(x * 2 + 1 , mid + 1 , r , L , R , val);
mx[x] = max(mx[x * 2] , mx[x * 2+ 1]);
mn[x] = min(mn[x * 2] , mn[x * 2 + 1]);
}
void upMax(int x , int l , int r , int L , int R , int val){
push(x , l != r);
if(l > R || L > r || mn[x] >= val)return;
if(L <= l && r <= R && mx[x] <= val){
lz[x] = val;push(x , l != r);
return;
}
int mid = l + r >> 1;
upMax(x * 2, l , mid , L , R , val);
upMax(x * 2 + 1 , mid + 1 , r , L , R , val);
mx[x] = max(mx[x * 2] , mx[x * 2+ 1]);
mn[x] = min(mn[x * 2] , mn[x * 2 + 1]);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
memset(lz,-1,sizeof lz);
for(int i = 0 ; i < k ; ++i){
if(op[i] == 1)upMax(1 , 1 , n , left[i] + 1 , right[i] + 1 , height[i]);
else upMin(1 , 1 , n , left[i] + 1, right[i] + 1 , height[i]);
}
function<void(int,int,int)> GetAns = [&](int x , int l , int r)->void{
push(x , l != r);
if(l == r){
finalHeight[l - 1] = mx[x];
return;
}
int mid = l + r >> 1;
GetAns(x * 2 , l , mid);
GetAns(x * 2 + 1 , mid + 1 , r);
};
GetAns(1 , 1 , n);
}
//int main()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// if(fopen(taskname".INP","r")){
// freopen(taskname".INP", "r",stdin);
// freopen(taskname".OUT", "w",stdout);
// }
//
//}
