#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;
int lazy=-1;
bool lazyOP=0;
int lazy2=-1;
bool lazy2OP=0;
void update(){
sum=left->sum+right->sum;
}
};
struct segtree {
int n;
node* root=new node{nullptr,nullptr,0,-1,false,-1,false};
void add(node* x, int v, bool t){
if(x->lazy<0){
x->lazyOP=t;
x->lazy=v;
}else if(x->lazy2<0) {
if(x->lazyOP==t) {
if(t==0) x->lazy=max(x->lazy,v);
else x->lazy=min(x->lazy,v);
}else{
x->lazy2OP=t;
x->lazy2=v;
}
}else if(x->lazy2OP==t){
if(t==0) x->lazy2=max(x->lazy2,v);
else x->lazy2=min(x->lazy2,v);
}else{
if(t==0) {
if(x->lazy2<=v){
x->lazy=x->lazy2;
x->lazyOP=x->lazy2OP;
x->lazy2=v;
x->lazy2OP=t;
}else{
if(x->lazy2>x->lazy) x->lazy=max(x->lazy,v);
}
}
else {
if(x->lazy2>=v){
x->lazy=x->lazy2;
x->lazyOP=x->lazy2OP;
x->lazy2=v;
x->lazy2OP=t;
}else{
if(x->lazy2<x->lazy) x->lazy=min(x->lazy,v);
}
}
}
}
void propagate(node* x){
if(x->lazy>-1){
if(x->left==nullptr){
if(x->lazyOP==0) x->sum=max(x->sum,x->lazy);
else x->sum=min(x->sum,x->lazy);
if(x->lazy2>-1){
if(x->lazy2OP==0) x->sum=max(x->sum,x->lazy2);
else x->sum=min(x->sum,x->lazy2);
x->lazy2=-1;
}
x->lazy=-1;
return;
}
if(x->lazy2>-1){
add(x->left,x->lazy,x->lazyOP);
add(x->right,x->lazy,x->lazyOP);
x->lazy=x->lazy2;
x->lazyOP=x->lazy2OP;
x->lazy2=-1;
}
add(x->left,x->lazy,x->lazyOP);
add(x->right,x->lazy,x->lazyOP);
x->lazy=-1;
}
}
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){
add(x,v,1);
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){
add(x,v,0);
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,-1,false,-1,false};
x->right=new node{nullptr,nullptr,0,-1,false,-1,false};
build(x->left,l,mid);
build(x->right,mid+1,r);
x->update();
}
int query(node* x, int l, int r, int p){
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;
}
