#include "wall.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
int n,q;
vector<pair<pair<int,int>,int>> qrs;
struct node {
node* left;
node* right;
int sum=0;
bool markedMN=false;
bool markedMX=false;
int lazy=0;
void update(){
sum=left->sum+right->sum;
}
};
struct segtree {
int n;
node* root=new node{nullptr,nullptr,0,false,false,0};
void propagate(node* x){
if(x->markedMN){
if(x->left==NULL){
x->sum=min(x->sum,x->lazy);
x->markedMN=false;
return;
}
if(x->left->markedMN){
x->left->lazy=min(x->left->lazy, x->lazy);
}else {
if(x->left->markedMX) propagate(x->left);
x->left->lazy=x->lazy;
x->left->markedMN=true;
}
if(x->right->markedMN){
x->right->lazy=min(x->right->lazy, x->lazy);
}else {
if(x->right->markedMX) propagate(x->right);
x->right->lazy=x->lazy;
x->right->markedMN=true;
}
x->markedMN=false;
x->lazy=0;
}else if(x->markedMX){
if(x->left==NULL){
x->sum=max(x->sum,x->lazy);
x->markedMX=false;
return;
}
if(x->left->markedMX){
x->left->lazy=max(x->left->lazy, x->lazy);
}else {
if(x->left->markedMN) propagate(x->left);
x->left->lazy=x->lazy;
x->left->markedMX=true;
}
if(x->right->markedMX){
x->right->lazy=max(x->right->lazy, x->lazy);
}else {
if(x->right->markedMN) propagate(x->right);
x->right->lazy=x->lazy;
x->right->markedMX=true;
}
x->markedMX=false;
x->lazy=0;
}
}
void updateMN(node* x, int l, int r, int qL, int qR, int v){
if(l>qR||r<qL) return;
propagate(x);
if(l>=qL&&r<=qR){
x->lazy=v;
x->markedMN=true;
return;
}
int mid=(l+r)/2;
updateMN(x->left,l,mid,qL,qR,v);
updateMN(x->right,mid+1,r,qL,qR,v);
x->update();
}
void updateMX(node* x, int l, int r, int qL, int qR, int v){
if(l>qR||r<qL) return;
propagate(x);
if(l>=qL&&r<=qR){
x->lazy=v;
x->markedMX=true;
return;
}
int mid=(l+r)/2;
updateMX(x->left,l,mid,qL,qR,v);
updateMX(x->right,mid+1,r,qL,qR,v);
x->update();
}
void build(node* x, int l, int r){
if(l==r){
x->sum=0;
return;
}
int mid=(l+r)/2;
x->left=new node{nullptr,nullptr,0,false,false,0};
x->right=new node{nullptr,nullptr,0,false,false,0};
build(x->left,l,mid);
build(x->right,mid+1,r);
x->update();
}
int query(node* x, int l, int r, int p){
if(r<p||l>p) return -1e9;
propagate(x);
if(l==p&&r==p) return x->sum;
int mid=(l+r)/2;
if(mid>=p) return query(x->left,l,mid,p);
else return query(x->right,mid+1,r,p);
}
void updateMN(int l, int r, int v){
updateMN(root,0,n-1,l,r,v);
}
void updateMX(int l, int r, int v){
updateMX(root,0,n-1,l,r,v);
}
int query(int p){
return query(root,0,n-1,p);
}
segtree(int x){
n=x;
build(root,0,n-1);
}
};
void buildWall(signed _n, signed _k, signed _op[], signed _left[], signed _right[], signed _height[], signed finalHeight[]){
n=_n; q=_k;
qrs.resize(q);
segtree seg(n);
for (int i = 0; i < q; i++)
{
int l=_left[i]; int r=_right[i];
if(_op[i]==1) seg.updateMX(l,r,_height[i]);
else seg.updateMN(l,r,_height[i]);
}
for (int i = 0; i < n; i++) finalHeight[i]=seg.query(i);
return;
}
