#include "wall.h"
#include<bits/stdc++.h>
#define MAXK 500005
#define F first
#define S second
#define INF 1000000007
using namespace std;
typedef pair<pair<int,int>,int> pa;
int n,k,op[MAXK],l[MAXK],r[MAXK],h[MAXK];
pa v;
struct node{
int val;
pa lazy;
node *l, *r;
};
node top;
void build(node *pos,int be,int ed){
if(be == ed){
pos->val = 0;
pos->lazy = {{-INF,INF},0};
return;
}
pos->l = new node, pos->r = new node;
int mid = (be+ed) / 2;
build(pos->l,be,mid), build(pos->r,mid+1,ed);
pos->lazy = {{-INF,INF},0};
}
pa merge(pa A,pa B){ // A = OLD, B = NEW
//printf("(%d %d) , (%d %d)",A.F,A.S,B.F,B.S);
if(A.F.F >= B.F.F && A.F.S <= B.F.S);
else if(A.F.F > B.F.F){
A.F.S = B.F.S;
if(A.F.F > A.F.S) A.F.F = -INF, A.S = 1;
}
else if(A.F.S < B.F.S){
A.F.F = B.F.F;
if(A.F.F > A.F.S) A.F.S = INF, A.S = 1;
}
else A.F = B.F;
A.S = max(A.S,B.S);
//printf(" : %d %d\n",A.F,A.S);
return A;
}
void update(node *pos,int be,int ed,int x,int y,int o,int i){
if(pos->lazy != make_pair(make_pair(-INF,INF),0)){
v = pos->lazy;
pos->lazy = {{-INF,INF},0};
if(be != ed) pos->l->lazy = merge(pos->l->lazy,v), pos->r->lazy = merge(pos->r->lazy,v);
else{
if(v.S == 0){
if(pos->val < v.F.F) pos->val = v.F.F;
else if(pos->val > v.F.S) pos->val = v.F.S;
}
else{
if(pos->val < v.F.F || v.F.S == INF) pos->val = v.F.F;
else if(pos->val > v.F.S || v.F.F == -INF) pos->val = v.F.S;
}
}
}
if(be > ed || ed < x || y < be) return;
if(x <= be && ed <= y){
v = (o == 1) ? make_pair(make_pair(i,INF),0) : make_pair(make_pair(-INF,i),0);
if(be != ed) pos->l->lazy = merge(pos->l->lazy,v), pos->r->lazy = merge(pos->r->lazy,v);
else{
if(v.S == 0){
if(pos->val < v.F.F) pos->val = v.F.F;
else if(pos->val > v.F.S) pos->val = v.F.S;
}
else{
if(pos->val < v.F.F || v.F.S == INF) pos->val = v.F.F;
else if(pos->val > v.F.S || v.F.F == -INF) pos->val = v.F.S;
}
}
return;
}
int mid = (be+ed)/2;
update(pos->l,be,mid,x,y,o,i), update(pos->r,mid+1,ed,x,y,o,i);
}
int query(node *pos,int be,int ed,int x){
if(pos->lazy != make_pair(make_pair(-INF,INF),0)){
v = pos->lazy;
pos->lazy = {{-INF,INF},0};
if(be != ed) pos->l->lazy = merge(pos->l->lazy,v), pos->r->lazy = merge(pos->r->lazy,v);
else{
if(v.S == 0){
if(pos->val < v.F.F) pos->val = v.F.F;
else if(pos->val > v.F.S) pos->val = v.F.S;
}
else{
if(pos->val < v.F.F || v.F.S == INF) pos->val = v.F.F;
else if(pos->val > v.F.S || v.F.F == -INF) pos->val = v.F.S;
}
}
}
if(be > ed || ed < x || x < be) return -INF;
if(be == ed) return pos->val;
int mid = (be+ed)/2;
return max(query(pos->l,be,mid,x), query(pos->r,mid+1,ed,x));
}
void buildWall(int N, int K, int OP[], int left[], int right[], int height[], int finalHeight[]){
n = N, k = K;
for(int i=1;i<=k;i++) op[i] = OP[i-1], l[i] = left[i-1]+1, r[i] = right[i-1]+1, h[i] = height[i-1];
build(&top,1,n);
for(int i=1;i<=k;i++){
update(&top,1,n,l[i],r[i],op[i],h[i]);
//for(int i=1;i<=n;i++) printf("%d ",query(&top,1,n,i));
//printf("\n\n");
}
for(int i=1;i<=n;i++){
finalHeight[i-1] = query(&top,1,n,i);
}
return;
}
