#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin() , x.end()
#define sz(x) (int)x.begin()
const int N = 2e6 + 7;
const int inf = 1e9 + 7;
pair < int , int > tree[4*N+7];
void init(){
for(int i = 0;i<4*N+7;i++){
tree[i] = {0,inf};
}
}
pair < int , int > merge(pair < int , int > &a , pair < int , int > &b){
pair < int , int > c;
c.first = max(a.first , b.first);
c.second = min(a.second , b.second);
// cout << "noluo : " << c.first << " " << c.second << endl;
if(c.first > c.second and a.first < b.first)
c = {a.second , a.second};
else if(c.first > c.second)
c = {a.first , a.first};
return c;
}
void push(int ind , int l , int r){
if(tree[ind] != make_pair(0,inf)){
if(l != r){
tree[ind*2] = merge(tree[ind] , tree[ind*2]);
tree[ind*2+1] = merge(tree[ind] , tree[ind*2+1]);
tree[ind] = {0,inf};
}
}
}
void update(int ql , int qr , pair < int , int > ran , int ind=1 , int l=0 , int r=N){
push(ind,l,r);
if(l >= ql and r <= qr){
// cout << "wtf : " << tree[ind].first << "," << tree[ind].second << " / " << ran.first << " " << ran.second << endl;
auto tf = merge(ran , tree[ind]);
// cout << "tf : " << tf.first << " " << tf.second << endl;
tree[ind] = tf;
// cout << "added " << l << " " << r << " " << tree[ind].first << " " << tree[ind].second << endl;
push(ind,l,r);
return;
}
else if(l > qr or r < ql)return;
int mid = (l + r) / 2;
update(ql,qr,ran,ind*2,l,mid);
update(ql,qr,ran,ind*2+1,mid+1,r);
}
pair < int , int > query(int qp , int ind=1 , int l=0 , int r=N){
push(ind,l,r);
if(l == r)return tree[ind];
int mid = (l + r) / 2;
if(qp <= mid)return query(qp,ind*2,l,mid);
else return query(qp,ind*2+1,mid+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
init();
for(int i = 0;i<n;i++)update(i,i,{0,0});
// cout << "segt : "<<endl;
// for(int j = 0;j<n;j++){
// auto bruh = query(j);
// cout << bruh.first << " ";
// }
// cout << endl;
// cout << endl;
for(int i = 0;i<k;i++){
// cout << "update : " << op[i] << " " << left[i] << " " << right[i] << " " << height[i] << endl;
if(op[i] == 1){// height , inf
update(left[i] , right[i] , {height[i] , inf});
}
else{// 0 , height
update(left[i] , right[i] , {0 , height[i]});
}
// cout << "segt : "<<endl;
// for(int j = 0;j<n;j++){
// auto bruh = query(j);
// cout << bruh.first << "," << bruh.second << " ";
// }
// cout << endl;
// cout << endl;
}
for(int i = 0;i<n;i++){
finalHeight[i] = query(i).first;
}
}
