#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
using vi = vector<int>;
using pi = pair<int, int>;
struct SegTree {
int n;
vi arr;
vector<pi> st;
SegTree() {}
SegTree(int n_, const vi& a) : n(n_), arr(a), st(4 * n_, {INT_MIN, INT_MAX}) {
build(1, 0, n);
}
pi combine(pi a, pi b) { return {max(a.first, b.first), min(a.second, b.second)}; }
pi build(int p, int l, int r) {
if (l + 1 == r) return st[p] = {arr[l], arr[l]};
int m = (l + r) >> 1;
return st[p] = combine(build(p << 1, l, m), build(p << 1 | 1, m, r));
}
pi query2(int p, 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[p];
int m = (l + r) >> 1;
return combine(query2(p << 1, l, m, ql, qr), query2(p << 1 | 1, m, r, ql, qr));
}
int query_max(int l, int r) {
if (l >= r) return INT_MIN;
return query2(1, 0, n, l, r).first;
}
};
static const int MAXN = 100000;
static const int INF = 1000000000;
int n;
vi h, idx, first_left, first_right;
int delta_left[MAXN], delta_right[MAXN];
SegTree st;
bitset<100000> fwd_alive, rev_alive;
int rpos(int i) { return (int)rev_alive.size() - i - 1; }
struct Event {
int y;
int key;
int w;
};
struct Wavelet {
int lo, hi;
vector<int> left_cnt;
vector<int> pref_sum;
Wavelet *lch = nullptr, *rch = nullptr;
Wavelet() : lo(0), hi(-1) {}
Wavelet(const vector<int>& vals, const vector<int>& ws, int lo_, int hi_) : lo(lo_), hi(hi_) {
int m = (int)vals.size();
left_cnt.resize(m + 1, 0);
pref_sum.resize(m + 1, 0);
for (int i = 0; i < m; i++) {
pref_sum[i + 1] = pref_sum[i] + ws[i];
}
if (m == 0 || lo == hi) return;
int mid = (lo + hi) >> 1;
vector<int> lv, rv, lw, rw;
lv.reserve(m);
rv.reserve(m);
lw.reserve(m);
rw.reserve(m);
for (int i = 0; i < m; i++) {
bool go_left = vals[i] <= mid;
left_cnt[i + 1] = left_cnt[i] + (go_left ? 1 : 0);
if (go_left) {
lv.push_back(vals[i]);
lw.push_back(ws[i]);
} else {
rv.push_back(vals[i]);
rw.push_back(ws[i]);
}
}
if (!lv.empty()) lch = new Wavelet(lv, lw, lo, mid);
if (!rv.empty()) rch = new Wavelet(rv, rw, mid + 1, hi);
}
int query_ge_prefix(int pos, int k) const {
if (pos <= 0 || hi < k) return 0;
if (lo >= k) return pref_sum[pos];
if (lo == hi) return 0;
int left_pos = left_cnt[pos];
int right_pos = pos - left_pos;
int ans = 0;
if (lch) ans += lch->query_ge_prefix(left_pos, k);
if (rch) ans += rch->query_ge_prefix(right_pos, k);
return ans;
}
};
struct XNode {
vector<Event> raw;
vector<int> ys;
Wavelet* wt = nullptr;
};
vector<XNode> xs;
vi all_keys;
bool built = false;
void add_event_to_x(int p, int l, int r, int ql, int qr, int y, int key, int w) {
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr) {
xs[p].raw.push_back({y, key, w});
return;
}
int m = (l + r) >> 1;
add_event_to_x(p << 1, l, m, ql, qr, y, key, w);
add_event_to_x(p << 1 | 1, m, r, ql, qr, y, key, w);
}
void add_interval_rect(int x1, int x2, int y1, int y2, int key) {
if (x1 > x2 || y1 > y2) return;
add_event_to_x(1, 0, n, x1, x2 + 1, y1, key, +1);
if (y2 + 1 < n) add_event_to_x(1, 0, n, x1, x2 + 1, y2 + 1, key, -1);
}
void build_node(int p) {
auto& v = xs[p].raw;
if (v.empty()) return;
sort(all(v), [](const Event& a, const Event& b) {
if (a.y != b.y) return a.y < b.y;
if (a.key != b.key) return a.key < b.key;
return a.w < b.w;
});
vector<int> vals, ws;
vals.reserve(v.size());
ws.reserve(v.size());
xs[p].ys.reserve(v.size());
for (auto& e : v) {
xs[p].ys.push_back(e.y);
vals.push_back(e.key);
ws.push_back(e.w);
}
xs[p].wt = new Wavelet(vals, ws, 0, (int)all_keys.size() - 1);
}
void build_all_xnodes(int p, int l, int r) {
build_node(p);
if (l + 1 == r) return;
int m = (l + r) >> 1;
build_all_xnodes(p << 1, l, m);
build_all_xnodes(p << 1 | 1, m, r);
}
int key_index_for_D(int D) {
return (int)(lower_bound(all(all_keys), D) - all_keys.begin());
}
int query_point(int p, int l, int r, int x, int y, int key_lb) {
int ans = 0;
if (xs[p].wt) {
int pos = (int)(upper_bound(all(xs[p].ys), y) - xs[p].ys.begin());
if (key_lb < (int)all_keys.size()) ans += xs[p].wt->query_ge_prefix(pos, key_lb);
}
if (l + 1 == r) return ans;
int m = (l + r) >> 1;
if (x < m) ans += query_point(p << 1, l, m, x, y, key_lb);
else ans += query_point(p << 1 | 1, m, r, x, y, key_lb);
return ans;
}
void build_everything() {
if (built) return;
built = true;
fwd_alive.reset();
rev_alive.reset();
for (int i : idx) {
int nxt = (int)fwd_alive._Find_next(i);
int rev = (int)rev_alive._Find_next(rpos(i));
int prv = (rev >= (int)rev_alive.size() ? -1 : (int)rev_alive.size() - rev - 1);
first_left[i] = prv;
first_right[i] = min(n, nxt);
delta_left[i] = (prv < 0 ? INF : st.query_max(prv, i + 1) - h[i]);
delta_right[i] = (nxt >= n ? INF : st.query_max(i, nxt + 1) - h[i]);
fwd_alive.set(i);
rev_alive.set(rpos(i));
}
vector<int> keys;
keys.reserve(3 * n);
for (int i = 0; i < n; i++) {
keys.push_back(min(delta_left[i], delta_right[i]));
keys.push_back(delta_left[i]);
keys.push_back(delta_right[i]);
}
sort(all(keys));
keys.erase(unique(all(keys)), keys.end());
all_keys = keys;
xs.assign(4 * max(1, n), {});
for (int i = 0; i < n; i++) {
int fl = first_left[i];
int fr = first_right[i];
// Condition 1:
// fl >= L && fr <= R && min(dl,dr) >= D
// Rectangle in (L,R): [0..fl] x [fr..n-1]
if (fl >= 0 && fr < n) {
int key = key_index_for_D(min(delta_left[i], delta_right[i]));
add_interval_rect(0, fl, fr, n - 1, key);
}
// Condition 2:
// i in [L,R], fl < L, fr <= R, delta_right >= D
// Rectangle: [fl+1..i] x [fr..n-1]
if (fr < n) {
int x1 = fl + 1;
int x2 = i;
if (x1 <= x2) {
int key = key_index_for_D(delta_right[i]);
add_interval_rect(x1, x2, fr, n - 1, key);
}
}
// Condition 3:
// i in [L,R], fl >= L, fr > R, delta_left >= D
// Rectangle: [0..fl] x [i..fr-1]
if (fl >= 0) {
int y1 = i;
int y2 = fr - 1;
if (y1 <= y2) {
int key = key_index_for_D(delta_left[i]);
add_interval_rect(0, fl, y1, y2, key);
}
}
}
build_all_xnodes(1, 0, n);
}
void init(int N, vi H) {
n = N;
h = H;
idx.resize(n);
iota(all(idx), 0);
sort(all(idx), [&](int i, int j) { return h[i] < h[j]; });
first_left.assign(n, -1);
first_right.assign(n, n);
st = SegTree(n, h);
built = false;
xs.clear();
all_keys.clear();
}
int max_towers(int L, int R, int D) {
build_everything();
int k = key_index_for_D(D);
if (k >= (int)all_keys.size()) return 1;
return 1 + query_point(1, 0, n, L, R, k);
}
