#include "wall.h"
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <assert.h>
using namespace std;
int all[1000005]={0};
struct A
{
int l,r;
int nxl,nxr;
int big;
int small;
//int bbig1
//int ssmall;
int which;
int last;
int ok;
}Node[8000005];
int now=1;
vector < int > tt;
void build(int l,int r,int here)
{
Node[here].l=l;
Node[here].r=r;
Node[here].small=0;
Node[here].big=0;
Node[here].last=1;
Node[here].ok=0;
if(l==r)
{
Node[here].which=0;
return ;
}
Node[here].nxl=now++;
Node[here].nxr=now++;
build(l,(l+r)/2,Node[here].nxl);
build((l+r)/2+1,r,Node[here].nxr);
}
void UPD(int here)
{
if(Node[here].last==1)
{
if(Node[Node[here].nxl].big>Node[here].big)
{
Node[Node[here].nxl].big=Node[here].big;
Node[Node[here].nxl].last=2;
}
if(Node[Node[here].nxl].small<Node[here].small)
{
Node[Node[here].nxl].small=Node[here].small;
Node[Node[here].nxl].last=1;
}
if(Node[Node[here].nxl].small>Node[Node[here].nxl].big)
{
if(Node[Node[here].nxl].last==1) Node[Node[here].nxl].big=Node[Node[here].nxl].small;
else Node[Node[here].nxl].small=Node[Node[here].nxl].big;
//Node[Node[here].nxl].last=1;
}
if(Node[Node[here].nxr].big>Node[here].big)
{
Node[Node[here].nxr].big=Node[here].big;
Node[Node[here].nxr].last=2;
}
if(Node[Node[here].nxr].small<Node[here].small)
{
Node[Node[here].nxr].small=Node[here].small;
Node[Node[here].nxr].last=1;
}
if(Node[Node[here].nxr].small>Node[Node[here].nxr].big)
{
if(Node[Node[here].nxr].last==1) Node[Node[here].nxr].big=Node[Node[here].nxr].small;
else Node[Node[here].nxr].small=Node[Node[here].nxr].big;
}
}
else
{
if(Node[Node[here].nxl].small<Node[here].small)
{
Node[Node[here].nxl].small=Node[here].small;
Node[Node[here].nxl].last=1;
}
if(Node[Node[here].nxl].big>Node[here].big)
{
Node[Node[here].nxl].big=Node[here].big;
Node[Node[here].nxl].last=2;
}
if(Node[Node[here].nxl].small>Node[Node[here].nxl].big)
{
if(Node[Node[here].nxl].last==1) Node[Node[here].nxl].big=Node[Node[here].nxl].small;
else Node[Node[here].nxl].small=Node[Node[here].nxl].big;
}
if(Node[Node[here].nxr].small<Node[here].small)
{
Node[Node[here].nxr].small=Node[here].small;
Node[Node[here].nxr].last=1;
}
if(Node[Node[here].nxr].big>Node[here].big)
{
Node[Node[here].nxr].big=Node[here].big;
Node[Node[here].nxr].last=2;
}
if(Node[Node[here].nxr].small>Node[Node[here].nxr].big)
{
if(Node[Node[here].nxr].last==1) Node[Node[here].nxr].big=Node[Node[here].nxr].small;
else Node[Node[here].nxr].small=Node[Node[here].nxr].big;
}
}
}
int Find(int where,int here)
{
if(where==Node[here].l&&where==Node[here].r)
{
if(Node[here].last==1) return Node[here].small;
return Node[here].big;
}
UPD(here);
if(where<=(Node[here].l+Node[here].r)/2) return Find(where,Node[here].nxl);
else return Find(where,Node[here].nxr);
}
void cha(int l,int r,int con,int what,int here)
{
if(Node[here].l==l&&Node[here].r==r)
{
if(what==1)
{
if(con>Node[here].small)
{
Node[here].small=con;
Node[here].last=what;
}
if(Node[here].small>Node[here].big)
{
Node[here].big=Node[here].small;
Node[here].last=what;
}
}
else
{
if(con<Node[here].big)
{
Node[here].big=con;
Node[here].last=what;
}
if(Node[here].small>Node[here].big)
{
Node[here].small=Node[here].big;
Node[here].last=what;
}
}
return ;
}
UPD(here);
if(r<=(Node[here].l+Node[here].r)/2) cha(l,r,con,what,Node[here].nxl);
else if(l>(Node[here].l+Node[here].r)/2) cha(l,r,con,what,Node[here].nxr);
else
{
cha(l,(Node[here].l+Node[here].r)/2,con,what,Node[here].nxl);
cha((Node[here].l+Node[here].r)/2+1,r,con,what,Node[here].nxr);
}
Node[here].big=max(Node[Node[here].nxl].big,Node[Node[here].nxr].big);
Node[here].small=min(Node[Node[here].nxl].small,Node[Node[here].nxr].small);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
int i,j;
build(0,n-1,0);
for(i=0;i<k;i++) cha(left[i],right[i],height[i],op[i],0);
for(i=0;i<n;i++) finalHeight[i]=Find(i,0);
return;
}
