#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
using vi = vector<int>;
using pi = pair<int, int>;
struct SegTree {
#define midpoint (l+(r-l)/2)
#define is_leaf (l+1==r)
#define left_child 2*i+1, l, midpoint
#define right_child 2*i+2, midpoint, r
#define query_root 0, 0, n
int n;
vi arr;
vector<pi> st;
SegTree() {}
SegTree(int n, const vi& arr) : n(n), arr(arr), st(4 * n, make_pair(INT_MIN, INT_MAX)) {
build(query_root);
}
pi combine(pi a, pi b) { return {max(a.first, b.first), min(a.second, b.second)}; }
pi build(int i, int l, int r) {
if (is_leaf) return st[i] = {arr[l], arr[l]};
return st[i] = combine(build(left_child), build(right_child));
}
int query(int ql, int qr, bool get_max = true) {
if (ql >= qr) return get_max ? INT_MIN : INT_MAX;
auto v = query(query_root, ql, qr);
return get_max ? v.first : v.second;
}
pi query(int i, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return {INT_MIN, INT_MAX};
if (ql <= l && r <= qr) return st[i];
return combine(query(left_child, ql, qr), query(right_child, ql, qr));
}
};
const int MAXN = 100000;
SegTree st;
int n;
vi h, idx, first_left, first_right;
int delta_left[MAXN], delta_right[MAXN];
bitset<100000> f, rbit;
int rpos(int i) { return (int)rbit.size() - i - 1; }
bool prepared = false;
struct InnerNode {
int l = 0, r = 0, sum = 0;
};
struct OuterNode {
int l = 0, r = 0, inner = 0;
};
vector<InnerNode> inner_nodes(1);
vector<OuterNode> outer_nodes(1);
int clone_inner(int p) {
inner_nodes.push_back(inner_nodes[p]);
return (int)inner_nodes.size() - 1;
}
int clone_outer(int p) {
outer_nodes.push_back(outer_nodes[p]);
return (int)outer_nodes.size() - 1;
}
int inner_update(int p, int l, int r, int pos) {
int u = clone_inner(p);
inner_nodes[u].sum++;
if (l + 1 == r) return u;
int m = (l + r) >> 1;
if (pos < m) inner_nodes[u].l = inner_update(inner_nodes[u].l, l, m, pos);
else inner_nodes[u].r = inner_update(inner_nodes[u].r, m, r, pos);
return u;
}
int inner_query(int p, int l, int r, int ql, int qr) {
if (!p || qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return inner_nodes[p].sum;
int m = (l + r) >> 1;
return inner_query(inner_nodes[p].l, l, m, ql, qr) +
inner_query(inner_nodes[p].r, m, r, ql, qr);
}
int outer_update(int p, int l, int r, int bpos, int apos) {
int u = clone_outer(p);
outer_nodes[u].inner = inner_update(outer_nodes[u].inner, 0, n, apos);
if (l + 1 == r) return u;
int m = (l + r) >> 1;
if (bpos < m) outer_nodes[u].l = outer_update(outer_nodes[u].l, l, m, bpos, apos);
else outer_nodes[u].r = outer_update(outer_nodes[u].r, m, r, bpos, apos);
return u;
}
int outer_query(int p, int l, int r, int ql, int qr, int apos_l) {
if (!p || qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) {
return inner_query(outer_nodes[p].inner, 0, n, apos_l, n);
}
int m = (l + r) >> 1;
return outer_query(outer_nodes[p].l, l, m, ql, qr, apos_l) +
outer_query(outer_nodes[p].r, m, r, ql, qr, apos_l);
}
vector<int> need_vals_desc;
vector<int> roots_by_need;
int version_for_D(int D) {
int lo = 0, hi = (int)need_vals_desc.size() - 1, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (need_vals_desc[mid] >= D) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}
void build_persistent_2d() {
if (prepared) return;
prepared = true;
f.reset();
rbit.reset();
for (int i : idx) {
int prev = rpos((int)rbit._Find_next(rpos(i)));
int nxt = (int)f._Find_next(i);
first_left[i] = prev;
first_right[i] = min(n, nxt);
int left = (prev < 0 ? (int)1e9 : st.query(prev, i + 1) - h[i]);
int right = (nxt >= n ? (int)1e9 : st.query(i, nxt + 1) - h[i]);
delta_left[i] = left;
delta_right[i] = right;
f.set(i);
rbit.set(rpos(i));
}
vector<tuple<int,int,int>> pts; // (need, b, a)
pts.reserve(n);
for (int i = 0; i < n; i++) {
if (first_left[i] >= 0 && first_right[i] < n) {
int need = min(delta_left[i], delta_right[i]);
pts.push_back({need, first_right[i], first_left[i]});
}
}
sort(all(pts), [&](const auto& x, const auto& y) {
return get<0>(x) > get<0>(y);
});
need_vals_desc.clear();
roots_by_need.clear();
int cur_root = 0;
int p = 0;
while (p < (int)pts.size()) {
int need = get<0>(pts[p]);
while (p < (int)pts.size() && get<0>(pts[p]) == need) {
int b = get<1>(pts[p]);
int a = get<2>(pts[p]);
cur_root = outer_update(cur_root, 0, n, b, a);
p++;
}
need_vals_desc.push_back(need);
roots_by_need.push_back(cur_root);
}
}
void init(int N, vector<int> H) {
n = N;
h = H;
idx.assign(n, 0);
iota(all(idx), 0);
first_left.assign(n, 0);
first_right.assign(n, 0);
sort(all(idx), [&](int i, int j) { return h[i] < h[j]; });
st = SegTree(n, h);
build_persistent_2d();
}
int max_towers(int L, int R, int D) {
int t = 1;
// First condition:
// first_left[i] >= L && first_right[i] <= R && min(delta_left[i], delta_right[i]) >= D
int ver = version_for_D(D);
if (ver != -1) {
t += outer_query(roots_by_need[ver], 0, n, 0, R + 1, L);
}
// Keep these two as-is.
for (int i = L; i <= R; i++) {
if (first_left[i] < L && first_right[i] <= R && delta_right[i] >= D) {t++;}
}
for (int i = R; i >= L; i--) {
if (first_left[i] >= L && first_right[i] > R && delta_left[i] >= D) {t++;}
}
return t;
}
