#include "wall.h"
#include <bits/stdc++.h>
#define pb push_back
#define fr first
#define sc second
#define mk make_pair
using namespace std;
const int N = (int) 2e5 + 6;
int nn;
vector <pair<int,pair<int,int> > > add,cut;
vector <int> mx,mn;
struct node {
int c,a;
node () {
c = 0,a = -1;
}
}t[N * 4],tt[N * 4];
void push (int v,int tl,int tr) {
if (t[v].a != -1 && tl < tr) {
if (t[v + v].a == -1) t[v + v].a = t[v].a;
if (t[v + v + 1].a == -1) t[v + v + 1].a = t[v].a;
t[v].a = -1;
}
}
void update (int l,int r,int h,int v = 1,int tl = 0,int tr = nn - 1) {
push(v,tl,tr);
if (tl > r || tr < l || t[v].a != -1)
return;
if (l <= tl && tr <= r) {
t[v].a = h;
push(v,tl,tr);
}
else {
int tm = (tl + tr) >> 1;
update (l,r,h,v + v,tl,tm);
update (l,r,h,v + v + 1,tm + 1,tr);
push(v,tl,tr);
push(v + v,tl,tm);
push(v + v + 1,tm + 1,tr);
}
}
void push1(int v,int tl,int tr) {
if (tt[v].a != -1 && tl < tr) {
if (tt[v + v].a == -1) tt[v + v].a = tt[v].a;
if (tt[v + v + 1].a == -1) tt[v + v + 1].a = tt[v].a;
tt[v].a = -1;
}
}
void update1 (int l,int r,int h,int v = 1,int tl = 0,int tr = nn - 1) {
push1(v,tl,tr);
if (tl > r || tr < l || tt[v].a != -1)
return;
if (l <= tl && tr <= r) {
tt[v].a = h;
push1(v,tl,tr);
}
else {
int tm = (tl + tr) >> 1;
update1 (l,r,h,v + v,tl,tm);
update1 (l,r,h,v + v + 1,tm + 1,tr);
push1(v,tl,tr);
push1(v + v,tl,tm);
push1(v + v + 1,tm + 1,tr);
}
}
void init (int v = 1,int tl = 0,int tr = nn - 1) {
push(v,tl,tr);
if (tl == tr) {
mx.pb(t[v].a);
}
else {
int tm = (tl + tr) >> 1;
init(v + v,tl,tm);
init(v + v + 1,tm + 1,tr);
}
}
void init1 (int v = 1,int tl = 0,int tr = nn - 1) {
push1(v,tl,tr);
if (tl == tr) {
mn.pb(tt[v].a);
}
else {
int tm = (tl + tr) >> 1;
init1(v + v,tl,tm);
init1(v + v + 1,tm + 1,tr);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
nn = n;
if (n <= 10000 && k <= 5000) {
for (int i = 0; i < k; i ++) {
int type = op[i];
int l = left[i];
int r = right[i];
int h = height[i];
if (type == 1) {
for (int j = l; j <= r; j ++)
finalHeight[j] = max(finalHeight[j],h);
}
else {
for (int j = l; j <= r; j ++)
finalHeight[j] = min(finalHeight[j],h);
}
}
}
else {
for (int i = 0; i < k; i ++) {
int type = op[i];
int l = left[i];
int r = right[i];
int h = height[i];
if (type == 1) add.pb({h,{l,r}});
else cut.pb({h,{l,r}});
}
sort (add.rbegin(),add.rend());
sort (cut.begin(),cut.end());
for (auto to : add)
update (to.sc.fr,to.sc.sc,to.fr);
for (auto to : cut)
update1 (to.sc.fr,to.sc.sc,to.fr);
init();
init1();
for (int i = 0; i < nn; i ++) {
finalHeight[i] = 0;
if (mx[i] != -1) finalHeight[i] = mx[i];
if (mn[i] != -1) finalHeight[i] = min(mn[i],finalHeight[i]);
}
}
}
