#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int nmax=1<<21,inf=1e9;
struct vert
{
int small,big,red/*forced reduce*/,add/*forced add*/;
//red>=add
};
vert tree[2*nmax+42];
void upd(int &node,int &_node)
{
/*
tree[_node].add=max(tree[_node].add,tree[node].add);
tree[_node].red=min(tree[_node].red,tree[node].red);
if(tree[_node].add>tree[_node].red)
{
tree[_node].add=tree[node].add;
tree[_node].red=tree[node].red;
}
*/
tree[_node].add=min(tree[_node].add,tree[node].red);
tree[_node].add=max(tree[_node].add,tree[node].add);
tree[_node].red=min(tree[_node].red,tree[node].red);
tree[_node].red=max(tree[_node].red,tree[node].add);
assert(tree[_node].add<=tree[_node].red);
}
int _;
void update_node(int &node)
{
if(tree[node].red==inf&&tree[node].add==0)return;
_=node*2;
upd(node,_);
_++;
upd(node,_);
tree[node].red=inf;
tree[node].add=0;
}
void update_add(int node,int l,int r,int lq,int rq,int h)
{
if(l==lq&&r==rq)
{
if(tree[node].add>=h)return;
if(tree[node].add<=h&&h<=tree[node].red)
{
tree[node].add=h;
tree[node].small=h;
return;
}
//tree[node].add<h
tree[node].add=h;
tree[node].red=h;
tree[node].small=h;
tree[node].big=h;
return;
}
update_node(node);
int av=(l+r)/2;
if(lq<=av)update_add(node*2,l,av,lq,min(av,rq),h);
if(av<rq)update_add(node*2+1,av+1,r,max(av+1,lq),rq,h);
tree[node].small=min(tree[node*2].small,tree[node*2+1].small);
tree[node].big=min(tree[node*2].big,tree[node*2+1].big);
}
void update_reduce(int node,int l,int r,int lq,int rq,int h)
{
if(l==lq&&r==rq)
{
if(tree[node].red<=h)return;
if(tree[node].red>=h&&h>=tree[node].add)
{
tree[node].red=h;
tree[node].big=h;
return;
}
//tree[node].red>h
tree[node].add=h;
tree[node].red=h;
tree[node].small=h;
tree[node].big=h;
return;
}
update_node(node);
int av=(l+r)/2;
if(lq<=av)update_reduce(node*2,l,av,lq,min(av,rq),h);
if(av<rq)update_reduce(node*2+1,av+1,r,max(av+1,lq),rq,h);
tree[node].small=min(tree[node*2].small,tree[node*2+1].small);
tree[node].big=min(tree[node*2].big,tree[node*2+1].big);
}
int cop[nmax];
void move_down(int node,int l,int r)
{
if(l==r)
{
cop[l]=tree[node].add;
return;
}
update_node(node);
int av=(l+r)/2;
move_down(node*2,l,av);
move_down(node*2+1,av+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[])
{
for(int i=1;i<2*nmax+42;i++)
tree[i].red=inf;
for(int i=0;i<k;i++)
{
if(op[i]==1)update_add(1,0,n-1,left[i],right[i],height[i]);
else update_reduce(1,0,n-1,left[i],right[i],height[i]);
/*
for(int j=1;j<=4*n;j++)
cout<<tree[j].small<<" "<<tree[j].big<<" "<<tree[j].red<<" "<<tree[j].add<<endl;
*/
}
move_down(1,0,n-1);
for(int j=0;j<n;j++)
finalHeight[j]=cop[j];
}
/*
const int n=10,k=6;
int op[k]={1,2,2,1,1,2};
int lef[k]={1,4,3,0,2,6};
int righ[k]={8,9,6,5,2,7};
int height[k]={4,1,5,3,5,0};
int fin[n];
int main()
{
buildWall(n,k,op,lef,righ,height,fin);
for(int i=0;i<n;i++)cout<<fin[i]<<" ";cout<<endl;
return 0;
}
*/
