#include "wall.h"
#include <algorithm>
using namespace std;
//#define int long long
#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define V st[cidx]
#define LC st[cidx*2]
#define RC st[cidx*2+1]
const int INF = 2147483647;
const int MAX = 2000010;
struct Node{
int sl, sr;
int tagl, tagr;
};
Node st[4*MAX];
void build(int cidx, int cl, int cr){
V.sl = cl;
V.sr = cr;
V.tagl = 0;
V.tagr = 0;
if(cl < cr){
int mid = (cl + cr) / 2;
build(cidx*2, cl, mid);
build(cidx*2+1, mid+1, cr);
}
}
void addtag(int cidx, int mmin, int mmax){
if(mmin > V.tagr){
V.tagl = V.tagr = mmin;
}
else if(mmax < V.tagl){
V.tagl = V.tagr = mmax;
}
else{
V.tagl = max(V.tagl, mmin);
V.tagr = min(V.tagr, mmax);
}
}
void pushtag(int cidx){
if(V.sl < V.sr){
addtag(cidx*2, V.tagl, V.tagr);
addtag(cidx*2+1, V.tagl, V.tagr);
}
V.tagl = -INF;
V.tagr = INF;
}
void modify(int cidx, int ml, int mr, int mmin, int mmax){
if(mr<V.sl or V.sr<ml){
return;
}
else if(ml<=V.sl and V.sr<=mr){
addtag(cidx, mmin, mmax);
return;
}
else{
pushtag(cidx);
modify(cidx*2, ml, mr, mmin, mmax);
modify(cidx*2+1, ml, mr, mmin, mmax);
}
}
int query(int cidx, int qidx){
if(V.sl==qidx and V.sr==qidx){
return V.tagl;
}
else{
pushtag(cidx);
int mid = (V.sl + V.sr) / 2;
if(qidx <= mid){
return query(cidx*2, qidx);
}
else{
return query(cidx*2+1, qidx);
}
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
build(1, 0, n-1);
FOR(i,0,k-1,1){
if(op[i]==1){ /// Max
modify(1, left[i], right[i], height[i], INF);
}
else if(op[i]==2){ /// min
modify(1, left[i], right[i], -INF, height[i]);
}
}
FOR(i,0,n-1,1){
finalHeight[i] = query(1, i);
}
}
