#include "wall.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
vector<int> st[N];
vector<int> nd[N];
struct SegTreeMAX{
vector<int> t;
vector<int> lazy;
int n;
SegTreeMAX(int size){
n = size;
t.assign(4*n,0);
lazy.assign(4*n,0);
}
void push(int v){
t[v*2] = max(t[v*2],lazy[v]);
lazy[v*2] = max(lazy[v*2],lazy[v]);
t[v*2+1] = max(t[v*2+1],lazy[v]);
lazy[v*2+1] = max(lazy[v*2+1],lazy[v]);
lazy[v] = 0;
}
void upd(int v,int tl,int tr,int l,int r,int val){
if(tr < l || r <tl){
return;
}
if(l <= tl && tr <= r){
t[v] = max(t[v],val);
lazy[v] = max(lazy[v],val);
return;
}
push(v);
int tm = (tl + tr)/2;
upd(v*2,tl,tm,l,r,val);
upd(v*2+1,tm+1,tr,l,r,val);
t[v] = max(t[v*2],t[v*2+1]);
}
int get(int v,int tl,int tr,int pos){
if(tl == tr){
return t[v];
}
push(v);
int tm = (tl + tr)/2;
if(pos <= tm){
return get(v*2,tl,tm,pos);
}
else return get(v*2+1,tm+1,tr,pos);
}
void upd(int l,int r,int val){
upd(1,0,n-1,l,r,val);
}
int get(int pos){
return get(1,0,n-1,pos);
}
};
struct SegTreeMIN{
vector<int> t;
vector<int> lazy;
int n;
SegTreeMIN(int size){
n = size;
t.assign(4*n,1e9);
lazy.assign(4*n,1e9);
}
void push(int v){
t[v*2] = min(t[v*2],lazy[v]);
lazy[v*2] = min(lazy[v*2],lazy[v]);
t[v*2+1] = min(t[v*2+1],lazy[v]);
lazy[v*2+1] = min(lazy[v*2+1],lazy[v]);
lazy[v] = 0;
}
void upd(int v,int tl,int tr,int l,int r,int val){
if(tr < l || r <tl){
return;
}
if(l <= tl && tr <= r){
t[v] = min(t[v],val);
lazy[v] = min(lazy[v],val);
return;
}
push(v);
int tm = (tl + tr)/2;
upd(v*2,tl,tm,l,r,val);
upd(v*2+1,tm+1,tr,l,r,val);
t[v] = min(t[v*2],t[v*2+1]);
}
int get(int v,int tl,int tr,int pos){
if(tl == tr){
return t[v];
}
push(v);
int tm = (tl + tr)/2;
if(pos <= tm){
return get(v*2,tl,tm,pos);
}
else return get(v*2+1,tm+1,tr,pos);
}
void upd(int l,int r,int val){
upd(1,0,n-1,l,r,val);
}
int get(int pos){
return get(1,0,n-1,pos);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 0;i<n;i++){
finalHeight[i] = 0;
}
if(n <= 10000 && k <= 5000){
for(int i = 0;i<k;i++){
for(int j = left[i];j<=right[i];j++){
if(op[i] == 1){
finalHeight[j] = max(finalHeight[j],height[i]);
}
else{
finalHeight[j] = min(finalHeight[j],height[i]);
}
}
}
}
else{
SegTreeMAX tmax(n);
SegTreeMIN tmin(n);
for(int i=0;i<k;i++){
if(op[i] == 1){
tmax.upd(left[i],right[i],height[i]);
}
else{
tmin.upd(left[i],right[i],height[i]);
}
}
for(int i = 0;i<n;i++){
finalHeight[i] = min(tmax.get(i),tmin.get(i));
}
}
return;
}
