#include "wall.h"
#include <algorithm>
#include <stdio.h>
using namespace std;
struct Node{
int mn,mx;
Node *chi[2];
};
Node *r;
void updateTree(int s,int e,Node *no,int ss,int ee,int k,bool m){
if(ss<=s && e<=ee){
if(m){
no->mx=min(no->mx,k);
no->mn=min(no->mn,no->mx);
}
else{
no->mn=max(no->mn,k);
no->mx=max(no->mx,no->mn);
}
return;
}
if(e<ss || ee<s) return;
int mid=(s+e)/2;
if(no->chi[0]==NULL) no->chi[0]=new Node();
if(no->chi[1]==NULL) no->chi[1]=new Node();
for(int i=0;i<2;i++){
no->chi[i]->mn=max(min(no->chi[i]->mn,no->mx),no->mn);
no->chi[i]->mx=min(max(no->chi[i]->mx,no->mn),no->mx);
}
updateTree(s,mid,no->chi[0],ss,ee,k,m);
updateTree(mid+1,e,no->chi[1],ss,ee,k,m);
no->mn=min(no->chi[0]->mn,no->chi[1]->mn);
no->mx=max(no->chi[0]->mx,no->chi[1]->mx);
}
void getTree(int s,int e,Node *no,int finalHeight[]){
if(s==e){
finalHeight[s]=no->mn;
return;
}
int mid=(s+e)/2;
if(no->chi[0]==NULL) no->chi[0]=new Node();
if(no->chi[1]==NULL) no->chi[1]=new Node();
for(int i=0;i<2;i++){
no->chi[i]->mn=max(min(no->chi[i]->mn,no->mx),no->mn);
no->chi[i]->mx=min(max(no->chi[i]->mx,no->mn),no->mx);
}
getTree(s,mid,no->chi[0],finalHeight);
getTree(mid+1,e,no->chi[1],finalHeight);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
int i;
r=new Node();
for(i=0;i<k;i++){
updateTree(0,n-1,r,left[i],right[i],height[i],op[i]-1);
}
getTree(0,n-1,r,finalHeight);
return;
}
