#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
vector< pii > up, down;
struct node{
int s, e, m, val, lazy;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1;
val = 0, lazy = -1;
if(s != e)l = new node(s, m), r = new node(m+1, e);
}
void propo(){
if(lazy != -1){
val = lazy;
if(s != e)l->lazy = lazy, r->lazy = lazy;
lazy = -1;
}
}
void upd(int a, int b, int c){
propo();
if(a == s && b == e)lazy = c;
else{
if(b <= m)l->upd(a, b, c);
else if(a > m)r->upd(a, b, c);
else l->upd(a, m, c), r->upd(m+1, b, c);
l->propo(), r->propo();
}
}
int query(int p){
propo();
if(s == e)return val;
else if(p <= m)return l->query(p);
else return r->query(p);
}
}*root;
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++){
if(op[i] == 1){
for(int j=left[i];j<=right[i];j++)finalHeight[j] = max(finalHeight[j], height[i]);
}
else{
for(int j=left[i];j<=right[i];j++)finalHeight[j] = min(finalHeight[j], height[i]);
}
}
return;
}
root = new node(0, n-1);
for(int i=0;i<k;i++){
if(op[i] == 1)up.push_back({height[i], {left[i], right[i]}});
else down.push_back({height[i], {left[i], right[i]}});
}
sort(up.begin(), up.end());
for(auto i : up)root->upd(i.se.fi, i.se.se, i.fi);
for(int i=0;i<n;i++){
int x = root->query(i);
down.push_back({x, {i, i}});
}
sort(down.begin(), down.end(), greater<>());
for(auto i : down)root->upd(i.se.fi, i.se.se, i.fi);
for(int i=0;i<n;i++)finalHeight[i] = root->query(i);
}
