#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
const int N=2000001;
const int INF=INT_MAX;
struct Node{
int sum;
int mx1;
int mx2;
int mn1;
int mn2;
int mxc;
int mnc;
};
Node st[N*4];
Node combine(Node &a,Node &b){
Node res;
res.sum=a.sum+b.sum;
if(a.mx1==b.mx1){
res.mx1=a.mx1;
res.mx2=max(a.mx2,b.mx2);
res.mxc=a.mxc+b.mxc;
}
else{
if(a.mx1>b.mx1){
res.mx1=a.mx1;
res.mx2=max(a.mx2,b.mx1);
res.mxc=a.mxc;
}
else{
res.mx1=b.mx1;
res.mx2=max(a.mx1,b.mx2);
res.mxc=b.mxc;
}
}
if(a.mn1==b.mn1){
res.mn1=a.mn1;
res.mn2=min(a.mn2,b.mn2);
res.mnc=a.mnc+b.mnc;
}
else{
if(a.mn1<b.mn1){
res.mn1=a.mn1;
res.mn2=min(a.mn2,b.mn1);
res.mnc=a.mnc;
}
else{
res.mn1=b.mn1;
res.mn2=min(a.mn1,b.mn2);
res.mnc=b.mnc;
}
}
return res;
}
void build(int idx,int l,int r){
if(l==r){
st[idx].sum=0;
st[idx].mx1=0;
st[idx].mx2=-INF;
st[idx].mn1=0;
st[idx].mn2=INF;
st[idx].mxc=1;
st[idx].mnc=1;
return;
}
int mid=(l+r)>>1;
build(2*idx,l,mid);
build(2*idx+1,mid+1,r);
st[idx]=combine(st[idx*2],st[idx*2+1]);
}
void apply_max(int idx,int val){
st[idx].sum-=(st[idx].mnc*st[idx].mn1);
st[idx].mn1=max(st[idx].mn1,val);
st[idx].mx1=max(st[idx].mx1,val);
st[idx].sum+=(st[idx].mnc*st[idx].mn1);
}
void push(int idx,int l,int r){
if(l!=r){
apply_max(2*idx,st[idx].mx1);
apply_max(2*idx+1,st[idx].mx1);
}
}
void upd_chmax(int idx,int l,int r,int ql,int qr,int val){
push(idx,l,r);
if(ql>r||l>qr||st[idx].mn1>=val) return;
else if(ql<=l&&r<=qr&&st[idx].mn2>val){
apply_max(idx,val);
push(idx,l,r);
return;
}
int mid=(l+r)>>1;
upd_chmax(2*idx,l,mid,ql,qr,val);
upd_chmax(2*idx+1,mid+1,r,ql,qr,val);
st[idx]=combine(st[idx*2],st[idx*2+1]);
}
int ask(int idx,int l,int r,int ql,int qr){
push(idx,l,r);
if(ql>r||l>qr) return 0;
else if(ql<=l&&r<=qr) return st[idx].sum;
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[])
{
build(1,0,n-1);
for(int i=0;i<k;i++){
if(op[i]==1) upd_chmax(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);
}
for(int i=0;i<k;i++){
if(op[i]==2){
for(int j=left[i];j<=right[i];j++) finalHeight[j]=min(finalHeight[j],height[i]);
}
}
return;
}
