#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define maxn 2000050
vector<int> seg(maxn*4,0);
vector<int> up(maxn*4,-1);
vector<int> down(maxn*4,INT_MAX);
vector<int> ans;
void push(int node){
up[node*2+1] = max(up[node*2+1],up[node]);
up[node*2+2] = max(up[node*2+2],up[node]);
down[node*2+1] = max(down[node*2+1],up[node]);
down[node*2+2] = max(down[node*2+2],up[node]);
down[node*2+1] = min(down[node*2+1],down[node]);
down[node*2+2] = min(down[node*2+2],down[node]);
up[node*2+1] = min(up[node*2+1],down[node]);
up[node*2+2] = min(up[node*2+2],down[node]);
up[node] = -1;
down[node] = INT_MAX;
}
void update(int node,int start,int end,int rangemin,int rangemax,int type,int val){
//cout << node << " " << start << " " << end << ' ' << rangemin << ' ' << rangemax << " " << type << " "<< val << endl;
if(start>=rangemin&&end<=rangemax){
//cout << " " << start " "
if(type==1){
up[node] = max(up[node],val);
down[node] = max(down[node],up[node]);
}
if(type==2){
down[node] = min(down[node],val);
up[node] = min(up[node],down[node]);
}
if(start==end){
if(up[node]!=-1){
seg[node] = max(seg[node],up[node]);
}
if(down[node]!=INT_MAX){
seg[node] = min(seg[node],down[node]);
}
up[node] = -1;
down[node] = INT_MAX;
}
return;
}
if(start==end){
if(up[node]!=-1){
seg[node] = max(seg[node],up[node]);
}
if(down[node]!=INT_MAX){
seg[node] = min(seg[node],down[node]);
}
up[node] = -1;
down[node] = INT_MAX;
return;
}
if(start>rangemax||end<rangemin){
//cout << " "<< start << " " << end << "---------\n";
return;
}
push(node);
int mid = (start+end)/2;
update(node*2+1,start,mid,rangemin,rangemax,type,val);
update(node*2+2,mid+1,end,rangemin,rangemax,type,val);
}
void print(int node,int start,int end){
//cout << up[node] << " "<< down[node] << " " << start << " " << end << "--\n";
if(start==end){
if(up[node]!=-1){
seg[node] = max(seg[node],up[node]);
}
if(down[node]!=INT_MAX){
seg[node] = min(seg[node],down[node]);
}
up[node] = -1;
down[node] = INT_MAX;
}
push(node);
if(start==end){
ans.push_back(seg[node]);
return;
}
int mid = (start+end)/2;
print(node*2+1,start,mid);
print(node*2+2,mid+1,end);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
int a,b,c,d;
for(int i=0;i<k;i++){
a = op[i];
b = left[i];
c = right[i];
d = height[i];
update(0,0,n-1,b,c,a,d);
}
print(0,0,n-1);
for(int i=0;i<n;i++){
finalHeight[i] = ans[i];
}
return;
}
