#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
const int N=2000001;
const int INF=INT_MAX;
int a[N];
struct Node{
int sum;
int mx1;
int mx2;
int mxc;
int mn1;
int mn2;
int mnc;
int lazy;
};
Node st[N*4];
void merge(int idx){
st[idx].sum=st[idx*2].sum+st[idx*2+1].sum;
if(st[idx*2].mx1==st[idx*2+1].mx1){
st[idx].mx1=st[idx*2].mx1;
st[idx].mx2=max(st[idx*2].mx2,st[idx*2+1].mx2);
st[idx].mxc=st[idx*2].mxc+st[idx*2+1].mxc;
}
else{
if(st[idx*2].mx1>st[idx*2+1].mx1){
st[idx].mx1=st[idx*2].mx1;
st[idx].mx2=max(st[idx*2].mx2,st[idx*2+1].mx1);
st[idx].mxc=st[idx*2].mxc;
}
else{
st[idx].mx1=st[idx*2+1].mx1;
st[idx].mx2=max(st[idx*2].mx1,st[idx*2+1].mx2);
st[idx].mxc=st[idx*2+1].mxc;
}
}
if(st[idx*2].mn1==st[idx*2+1].mn1){
st[idx].mn1=st[idx*2].mn1;
st[idx].mn2=min(st[idx*2].mn2,st[idx*2+1].mn2);
st[idx].mnc=st[idx*2].mnc+st[idx*2+1].mnc;
}
else{
if(st[idx*2].mn1<st[idx*2+1].mn1){
st[idx].mn1=st[idx*2].mn1;
st[idx].mn2=min(st[idx*2].mn2,st[idx*2+1].mn1);
st[idx].mnc=st[idx*2].mnc;
}
else{
st[idx].mn1=st[idx*2+1].mn1;
st[idx].mn2=min(st[idx*2].mn1,st[idx*2+1].mn2);
st[idx].mnc=st[idx*2+1].mnc;
}
}
}
void push_add(int idx,int l,int r,int val){
if(val==0) return;
st[idx].sum+=((r-l+1)*val);
st[idx].mx1+=val;
if(st[idx].mx2!=-INF) st[idx].mx2+=val;
st[idx].mn1+=val;
if(st[idx].mn2!=INF) st[idx].mn2+=val;
st[idx].lazy+=val;
}
void push_max(int idx,int val,bool l){
if(val>=st[idx].mx1) return;
st[idx].sum-=(st[idx].mxc*st[idx].mx1);
st[idx].mx1=val;
st[idx].sum+=(st[idx].mxc*st[idx].mx1);
if(l){
st[idx].mn1=st[idx].mx1;
}
else{
if(val<=st[idx].mn1) st[idx].mn1=val;
else if(val<st[idx].mn2) st[idx].mn2=val;
}
}
void push_min(int idx,int val,bool l){
if(val<=st[idx].mn1) return;
st[idx].sum-=(st[idx].mnc*st[idx].mn1);
st[idx].mn1=val;
st[idx].sum+=(st[idx].mnc*st[idx].mn1);
if(l){
st[idx].mx1=st[idx].mn1;
}
else{
if(val>=st[idx].mx1) st[idx].mx1=val;
else if(val>st[idx].mx2) st[idx].mx2=val;
}
}
void push_down(int idx,int l,int r){
if(l==r) return;
int mid=(l+r)>>1;
push_add(2*idx,l,mid,st[idx].lazy);
push_add(2*idx+1,mid+1,r,st[idx].lazy);
st[idx].lazy=0;
push_max(2*idx,st[idx].mx1,l==mid);
push_max(2*idx+1,st[idx].mx1,mid+1==r);
push_min(2*idx,st[idx].mn1,l==mid);
push_min(2*idx+1,st[idx].mn1,mid+1==r);
}
void build(int idx,int l,int r){
st[idx].lazy=0;
if(l==r){
st[idx].sum=a[l];
st[idx].mx1=st[idx].mn1=a[l];
st[idx].mxc=st[idx].mnc=1;
st[idx].mx2=-INF;
st[idx].mn2=INF;
return;
}
int mid=(l+r)>>1;
build(2*idx,l,mid);
build(2*idx+1,mid+1,r);
merge(idx);
}
void update_add(int idx,int l,int r,int ql,int qr,int val){
if(ql>r||l>qr) return;
else if(ql<=l&&r<=qr){
push_add(idx,l,r,val);
return;
}
push_down(idx,l,r);
int mid=(l+r)>>1;
update_add(2*idx,l,mid,ql,qr,val);
update_add(2*idx+1,mid+1,r,ql,qr,val);
merge(idx);
}
void update_chmin(int idx,int l,int r,int ql,int qr,int val){
if(ql>r||l>qr||val>=st[idx].mx1) return;
if(ql<=l&&r<=qr&&val>st[idx].mx2){
push_max(idx,val,l==r);
return;
}
push_down(idx,l,r);
int mid=(l+r)>>1;
update_chmin(2*idx,l,mid,ql,qr,val);
update_chmin(2*idx+1,mid+1,r,ql,qr,val);
merge(idx);
}
void update_chmax(int idx,int l,int r,int ql,int qr,int val){
if(ql>r||l>qr||val<=st[idx].mn1) return;
if(ql<=l&&r<=qr&&val<st[idx].mn2){
push_min(idx,val,l==r);
return;
}
push_down(idx,l,r);
int mid=(l+r)>>1;
update_chmax(2*idx,l,mid,ql,qr,val);
update_chmax(2*idx+1,mid+1,r,ql,qr,val);
merge(idx);
}
int ask(int idx,int l,int r,int ql,int qr){
if(ql>r||l>qr) return 0;
else if(ql<=l&&r<=qr) return st[idx].sum;
push_down(idx,l,r);
int mid=(l+r)>>1;
return ask(2*idx,l,mid,ql,qr)+ask(2*idx+1,mid+1,r,ql,qr);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
for(int i=0;i<n;i++) a[i]=0;
build(1,0,n-1);
for(int i=0;i<k;i++){
if(op[i]==1) update_chmax(1,0,n-1,left[i],right[i],height[i]);
if(op[i]==2) update_chmin(1,0,n-1,left[i],right[i],height[i]);
}
for(int i=0;i<n;i++) finalHeight[i]=ask(1,0,n-1,i,i);
return;
}
