#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 100;
template<typename T>
void dbg(const T& t){
cout<<t<<endl;
return;
}
template<typename T,typename... Args>
void dbg(const T& t,const Args&... args){
cout<<t<<" , ";
dbg(args...);
}
#define dbg(...) cout<<"("<<#__VA_ARGS__<<") : "<<endl;dbg(__VA_ARGS__);
struct Node
{
int min;
int max;
int smin;
int smax;
int lzmin=-1,lzmax=-1;
bool lazy=false;
Node* left,*right;
Node() : left(nullptr),right(nullptr){}
};
void pull(Node* node){
//for min
if (node->left->max == node->right->max) {
node->max = node->left->max;
node->smax = max(node->left->smax, node->right->smax);
} else {
if (node->left->max > node->right->max) {
node->max = node->left->max;
node->smax = max(node->left->smax, node->right->max);
} else {
node->max = node->right->max;
node->smax = max(node->left->max, node->right->smax);
}
}
// min
if (node->left->min == node->right->min) {
node->min = node->left->min;
node->smin = min(node->left->smin, node->right->smin);
} else {
if (node->left->min < node->right->min) {
node->min = node->left->min;
node->smin = min(node->left->smin, node->right->min);
} else {
node->min = node->right->min;
node->smin = min(node->left->min, node->right->smin);
}
}
}
void build(Node* node,int l,int r){
if(l==r){
node->min=node->max=0;
node->smin=1e9;
node->smax=-1e9;
return;
}
int mid=(l+r)/2;
node->left=new Node();
node->right=new Node();
build(node->left,l,mid);
build(node->right,mid+1,r);
pull(node);
}
void pmin(Node* node,int l,int r,int x){
if(node->max<=x) return;
node->max=x;
if(l==r){
node->min=node->max;
}else{
if(x<=node->min){
node->min=x;
}else if(x<node->smin){
node->smin=x;
}
}
}
void pmax(Node* node,int l,int r,int x){
if(node->min>=x)
return;
node->min=x;
if(l==r){
node->max=node->min;
}else{
if(x>=node->max){
node->max=x;
}else if(x>node->smax){
node->smax=x;
}
}
}
void push(Node* node,int l,int r){
if(l==r) return;
pmin(node->left,l,(l+r)/2,node->max);
pmin(node->right,(l+r)/2+1,r,node->max);
pmax(node->left,l,(l+r)/2,node->min);
pmax(node->right,(l+r)/2+1,r,node->min);
}
void p(Node* node,int l,int r){
push(node,l,r);
if(l==r) return;
pull(node);
}
void setmin(Node* node,int l,int r,int ql,int qr,int x){
p(node,l,r);
if(l>qr||r<ql) return;
if(node->max<=x) return;
if(ql<=l&&r<=qr&&node->smax<x){
//put tag
pmin(node,l,r,x);
return;
}
p(node,l,r);
int mid=(l+r)/2;
setmin(node->left,l,mid,ql,qr,x);
setmin(node->right,mid+1,r,ql,qr,x);
pull(node);
}
void setmax(Node* node,int l,int r,int ql,int qr,int x){
p(node,l,r);
if(l>qr||r<ql) return;
if(node->min>=x) return;
if(ql<=l&&r<=qr&&x<node->smin){
//put tag
pmax(node,l,r,x);
return;
}
p(node,l,r);
int mid=(l+r)/2;
setmax(node->left,l,mid,ql,qr,x);
setmax(node->right,mid+1,r,ql,qr,x);
pull(node);
}
int query(Node* node,int l,int r,int ql){
push(node,l,r);
if(l==r) return node->min;
int mid = (l+r)/2;
if(ql<=mid) return query(node->left,l,mid,ql);
else return query(node->right,mid+1,r,ql);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int ans[])
{
Node* root=new Node();
build(root,0,n-1);
for(int i=0;i<k;i++){
int t=op[i];
int l=left[i];
int r=right[i];
int x=height[i];
if(t==1){
setmax(root,0,n-1,l,r,x);
}else{
setmin(root,0,n-1,l,r,x);
}
}
for(int i=0;i<n;i++){
ans[i]=query(root,0,n-1,i);
}
return;
}
