#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fr first
#define se second
const int INF = 0x3f3f3f3f;
const int MAXK = 5e5 + 10;
struct Node {
int mi = INF, mx = 0;
};
int tipo[MAXK];
int v[MAXK];
Node seg[4*MAXK];
Node merge(Node a, Node b) {
Node ans;
ans.mi = min(a.mi, b.mi);
ans.mx = max(a.mx, b.mx);
return ans;
}
Node empt;
void setZero(int node, int l, int r, int po) {
if (l == r) {
seg[node] = empt;
return;
}
int m = (l + r)/2;
if (po <= m) setZero(2*node, l, m, po);
else setZero(2*node + 1, m + 1, r, po);
seg[node] = merge(seg[2*node], seg[2*node + 1]);
}
void setOn(int node, int l, int r, int po) {
if (l == r) {
seg[node] = empt;
if (tipo[po] == 1) seg[node].mx = v[l]; // we want the maximum of the adding phase (max)
else seg[node].mi = v[l];
return;
}
int m = (l + r)/2;
if (po <= m) setOn(2*node, l, m, po);
else setOn(2*node + 1, m + 1, r, po);
seg[node] = merge(seg[2*node], seg[2*node + 1]);
}
Node query(int node, int l, int r, int tl, int tr) {
if ((r < tl) || (tr < l)) return empt;
if ((tl <= l) && (r <= tr)) return seg[node];
int m = (l + r)/2;
return merge(query(2*node, l, m, tl, tr), query(2*node + 1, m + 1, r, tl, tr));
}
int bbin(int node, int l, int r, Node val) {
if (l == r) return l;
Node dir = merge(seg[2*node + 1], val);
int m = (l + r)/2;
if (dir.mx > dir.mi) return bbin(2*node + 1, m + 1, r, val);
return bbin(2*node, l, m, dir);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int fh[]){
// 1 is adding phase, 2 is removing phase
for (int i = 0; i < k; i++) tipo[i] = op[i];
for (int i = 0; i < k; i++) v[i] = h[i];
vector<vector<pii>> ops(n + 1);
for (int i = 0; i < k; i++) {
ops[l[i]].push_back({i, 1});
ops[r[i] + 1].push_back({i, 0});
}
int qtd = 0;
for (int i = 0; i < n; i++) {
for (auto u : ops[i]) {
if (u.se) setOn(1, 0, k - 1, u.fr);
else setZero(1, 0, k - 1, u.fr);
//cout << seg[1].mi << " " << seg[1].mx << "\n";
}
if (seg[1].mi >= seg[1].mx) {
fh[i] = seg[1].mx;
continue; // no intersection
}
int po = bbin(1, 0, k - 1, empt);
Node ans = query(1, 0 , k - 1, po + 1, k - 1);
if (tipo[po] == 1) fh[i] = ans.mi;
else fh[i] = ans.mx;
}
//for (int i = 0; i < n; i++) cout << fh[i] << " ";
//cout << "\n";
return;
}
