#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
const int N = 5e5 + 5;
const int M = 2e6 + 5;
pair<int,int> seg[N*4];
struct wall {
int h, ty, ord;
};
pair<int,int> mer(pair<int,int> a, pair<int,int> b) {
if(a.second < b.first) {
return {b.first,b.first};
}
else if(a.first > b.second) {
return {b.second,b.second};
}
else {
return {max(a.first,b.first),min(a.second,b.second)};
}
return {0,INF};
}
void Build(int x, int l, int r) {
if(l == r) {
seg[x].first = 0;
seg[x].second = INF;
}
else {
int mid = (l+r)/2;
Build(x*2,l,mid);
Build(x*2+1,mid+1,r);
seg[x].first = 0;
seg[x].second = INF;
}
}
void Update(int x, int l, int r, int pos, int ty, int val) {
if(l == r) {
if(val < 0) {
// cout << "aa" << endl;
if(ty == 1) seg[x].first = 0;
else seg[x].second = INF;
}
else {
// cout << "bb" << endl;
if(ty == 1) seg[x].first = val;
else seg[x].second = val;
}
// cout << seg[x].first << ' ' << seg[x].second << endl;
}
else {
int mid = (l+r)/2;
if(pos <= mid) Update(x*2,l,mid,pos,ty,val);
else Update(x*2+1,mid+1,r,pos,ty,val);
pair<int,int> pp = mer(seg[x*2],seg[x*2+1]);
// cout << l << ' ' << r << 'k' << endl;
// cout << pp.first << ' ' << pp.second << 'a' << endl;
seg[x] = pp;
}
}
vector<wall> v[M];
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
for(int i = 0; i < k; i++) {
if(op[i] == 1) {
wall cur;
cur.h = height[i]+1;
cur.ty = 1;
cur.ord = i+1;
v[left[i]].push_back(cur);
cur.h *= -1;
v[right[i]+1].push_back(cur);
}
else {
wall cur;
cur.h = height[i]+1;
cur.ty = 2;
cur.ord = i+1;
v[left[i]].push_back(cur);
cur.h *= -1;
v[right[i]+1].push_back(cur);
}
}
for(int i = 0; i < n; i++) finalHeight[i] = 1;
Build(1,1,k+1);
for(int i = 0; i < n; i++) {
for(auto j : v[i]) {
// cout << "JJJJJJJJJJJJJ" << endl;
// cout << j.ord << ' ' << j.h << 'p' << endl;
Update(1,1,k+1,j.ord,j.ty,j.h);
}
if(finalHeight[i] < seg[1].first) finalHeight[i] = seg[1].first;
if(finalHeight[i] > seg[1].second) finalHeight[i] = seg[1].second;
}
for(int i = 0; i < n; i++) finalHeight[i]--;
}
