#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 100;
struct Node{
int min;
int max;
int smin;
int smax;
} tree[4*maxn];
void pull(int node){
//for min
if (tree[node << 1].max == tree[node << 1 | 1].max) {
tree[node].max = tree[node << 1].max;
tree[node].smax = max(tree[node << 1].smax, tree[node << 1 | 1].smax);
} else {
if (tree[node << 1].max > tree[node << 1 | 1].max) {
tree[node].max = tree[node << 1].max;
tree[node].smax = max(tree[node << 1].smax, tree[node << 1 | 1].max);
} else {
tree[node].max = tree[node << 1 | 1].max;
tree[node].smax = max(tree[node << 1].max, tree[node << 1 | 1].smax);
}
}
// min
if (tree[node << 1].min == tree[node << 1 | 1].min) {
tree[node].min = tree[node << 1].min;
tree[node].smin = min(tree[node << 1].smin, tree[node << 1 | 1].smin);
} else {
if (tree[node << 1].min < tree[node << 1 | 1].min) {
tree[node].min = tree[node << 1].min;
tree[node].smin = min(tree[node << 1].smin, tree[node << 1 | 1].min);
} else {
tree[node].min = tree[node << 1 | 1].min;
tree[node].smin = min(tree[node << 1].min, tree[node << 1 | 1].smin);
}
}
}
void build(int node,int l,int r){
if(l==r){
tree[node].min=tree[node].max=0;
tree[node].smin=1e9;
tree[node].smax=-1e9;
return;
}
int mid=(l+r)/2;
build(node*2,l,mid);
build(node*2+1,mid+1,r);
pull(node);
}
void pmin(int node,int l,int r,int x){
if(tree[node].max<=x) return;
tree[node].max=x;
if(l==r){
tree[node].min=tree[node].max;
}else{
if(x<=tree[node].min){
tree[node].min=x;
}else if(x<tree[node].smin){
tree[node].smin=x;
}
}
}
void pmax(int node,int l,int r,int x){
if(tree[node].min>=x)
return;
tree[node].min=x;
if(l==r){
tree[node].max=tree[node].min;
}else{
if(x>=tree[node].max){
tree[node].max=x;
}else if(x>tree[node].smax){
tree[node].smax=x;
}
}
}
void push(int node,int l,int r){
if(l==r) return;
pmin(node*2,l,(l+r)/2,tree[node].max);
pmin(node*2+1,(l+r)/2+1,r,tree[node].max);
pmax(node*2,l,(l+r)/2,tree[node].min);
pmax(node*2+1,(l+r)/2+1,r,tree[node].min);
}
void setmin(int node,int l,int r,int ql,int qr,int x){
push(node,l,r);
if(l>qr||r<ql||tree[node].max<=x) return;
if(ql<=l&&r<=qr&&tree[node].smax<x){
//put tag
pmin(node,l,r,x);
return;
}
push(node,l,r);
int mid=(l+r)/2;
setmin(node*2,l,mid,ql,qr,x);
setmin(node*2+1,mid+1,r,ql,qr,x);
pull(node);
}
void setmax(int node,int l,int r,int ql,int qr,int x){
push(node,l,r);
if(l>qr||r<ql||tree[node].min>=x) return;
if(ql<=l&&r<=qr&&x<tree[node].smin){
//put tag
pmax(node,l,r,x);
return;
}
push(node,l,r);
int mid=(l+r)/2;
setmax(node*2,l,mid,ql,qr,x);
setmax(node*2+1,mid+1,r,ql,qr,x);
pull(node);
}
int query(int node,int l,int r,int ql){
push(node,l,r);
if(l==r) return tree[node].min;
int mid = (l+r)/2;
if(ql<=mid) return query(node*2,l,mid,ql);
else return query(node*2+1,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(1,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(1,0,n-1,l,r,x);
}else{
setmin(1,0,n-1,l,r,x);
}
}
for(int i=0;i<n;i++){
ans[i]=query(1,0,n-1,i);
}
return;
}
