#include "wall.h"
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const int maxK=5e5;
struct segtree{
int n;
vector<pair<int, int>>st;
segtree(int n):n(n), st(4*n){};
void update(int root, int l, int r, pair<int, int>val, int posi){
if(l==r){
st[root]=val;
return;
}
int mid=(l+r)/2;
if(posi<=mid) update(2*root, l, mid, val, posi);
else update(2*root+1, mid+1, r, val, posi);
int lefti;
if(st[2*root].first==-1) lefti=0;
else lefti=st[2*root].second;
st[root]=st[2*root];
if(st[2*root+1].first==1 && lefti<=st[2*root+1].second) st[root]=st[2*root+1];
if(st[2*root+1].first==2 && lefti>=st[2*root+1].second) st[root]=st[2*root+1];
}
}st(maxK+1);
const int maxN=2e6;
struct point{
int x, y, z;
};
vector<point>v [maxN+5];
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0 ; i<4*(maxK+1) ; i++){
st.st[i]={-1, -1};
}
for(int i=0 ; i<k ; i++){
v[left[i]].push_back({i, op[i], height[i]});
v[right[i]+1].push_back({i, -op[i], height[i]});
}
for(int i=0 ; i<n ; i++){
for(point it:v[i]){
if(it.y<0) st.update(1, 0, n-1, make_pair(-1, -1), it.x);
else st.update(1, 0, n-1, make_pair(it.y, it.z), it.x);
// cout<<i<<" "<<it.x<<" "<<it.y<<"\n";
}
if(st.st[1].first==-1) finalHeight[i]=0;
else finalHeight[i]=st.st[1].second;
}
return;
}
