#include "wall.h"
#include <bits/stdc++.h>
#define ii pair<int,int>
#define F first
#define S second
using namespace std;
const int N=2e6+100;
int mx[4*N];
int mx2[4*N];
int mn[4*N];
int mn2[4*N];
void chmn(int p,int s,int e,int h)
{
if(mn[p]>=h){
return;
}
mn[p]=h;
if(mx[p]<h){
mx[p]=h;
mx2[p]=-1e9;
}
else if(mx2[p]<h){
mx2[p]=h;
}
}
void chmx(int p,int s,int e,int h)
{
if(mx[p]<=h){
return;
}
mx[p]=h;
if(mn[p]>h){
mn[p]=h;
mn2[p]=1e9;
}
else if(mn2[p]<h){
mn2[p]=h;
}
}
void fix(int p,int s,int e)
{
if(s!=e){
int mid=(s+e)/2;
chmn(p*2,s,mid,mn[p]);
chmn(p*2+1,mid+1,e,mn[p]);
chmx(p*2,s,mid,mx[p]);
chmx(p*2+1,mid+1,e,mx[p]);
}
}
void com(int p,int s,int e)
{
int a[]={mn[p*2],mn[p*2+1],mn2[p*2],mn2[p*2+1]};
sort(a,a+4);
mn[p]=a[0];
mn2[p]=a[1]!=a[0] ? a[1] : a[2];
int b[]={mx[p*2],mx[p*2+1],mx2[p*2],mx2[p*2+1]};
sort(b,b+4);
mx[p]=b[3];
mx2[p]=b[2]!=b[3] ? b[2] : b[1];
}
void update(int p,int s,int e,int a,int b,int h,int t)
{
if(t==1){
fix(p,s,e);
if(s>b || e<a || mn[p]>=h){
return;
}
if( a<=s && e<=b && mn2[p]>h ){
chmn(p,s,e,h);
return;
}
int mid=(s+e)/2;
update(p*2,s,mid,a,b,h,t);
update(p*2+1,mid+1,e,a,b,h,t);
com(p,s,e);
}
else{
fix(p,s,e);
if(s>b || e<a || mx[p]<=h){
return;
}
if( a<=s && e<=b && mx2[p]<h ){
chmx(p,s,e,h);
return;
}
int mid=(s+e)/2;
update(p*2,s,mid,a,b,h,t);
update(p*2+1,mid+1,e,a,b,h,t);
com(p,s,e);
}
}
int get(int p,int s,int e,int i)
{
fix(p,s,e);
if(s==e){
return mx[p];
}
int mid=(s+e)/2;
if(i<=mid){
return get(p*2,s,mid,i);
}
else{
return get(p*2+1,mid+1,e,i);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for(int i=1;i<=4*n;i++){
mn[i]=mx[i]=0;
mn2[i]=1e9;
mx2[i]=-1e9;
}
for(int i=0;i<k;i++){
update(1,0,n-1,left[i],right[i],height[i],op[i]);
}
for(int i=0;i<n;i++){
finalHeight[i]=get(1,0,n-1,i);
}
//cout<<"\n";
}
// https://oj.uz/problem/submit/IOI14_wall
