#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
static const int INF = 1e9;
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 merge(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] = merge(build(p << 1, l, m), build(p << 1 | 1, m, r));
}
pi query2(int p, int l, int r, int ql, int qr) const {
if (qr <= l || r <= ql) return {INT_MIN, INT_MAX};
if (ql <= l && r <= qr) return st[p];
int m = (l + r) >> 1;
return {
max(query2(p << 1, l, m, ql, qr).first,
query2(p << 1 | 1, m, r, ql, qr).first),
min(query2(p << 1, l, m, ql, qr).second,
query2(p << 1 | 1, m, r, ql, qr).second)
};
}
int query_max(int l, int r) const {
if (l >= r) return INT_MIN;
return query2(1, 0, n, l, r).first;
}
};
struct PersistentRectCounter {
struct InnerNode {
int l = 0, r = 0, sum = 0;
};
struct OuterNode {
int l = 0, r = 0, inner = 0;
};
struct Point {
int key; // active iff key >= D
int x; // first_left + 1
int y; // first_right
};
int M = 0; // coordinates in [0, M)
vector<InnerNode> in;
vector<OuterNode> out;
vector<int> vals; // distinct keys, descending
vector<int> roots; // root for all points with key >= vals[i]
PersistentRectCounter() {}
int new_inner(int from) {
in.push_back(in[from]);
return (int)in.size() - 1;
}
int new_outer(int from) {
out.push_back(out[from]);
return (int)out.size() - 1;
}
int upd_inner(int node, int l, int r, int pos) {
int u = new_inner(node);
in[u].sum++;
if (l + 1 == r) return u;
int m = (l + r) >> 1;
if (pos < m) in[u].l = upd_inner(in[u].l, l, m, pos);
else in[u].r = upd_inner(in[u].r, m, r, pos);
return u;
}
int upd_outer(int node, int l, int r, int y, int x) {
int u = new_outer(node);
out[u].inner = upd_inner(out[u].inner, 0, M, x);
if (l + 1 == r) return u;
int m = (l + r) >> 1;
if (y < m) out[u].l = upd_outer(out[u].l, l, m, y, x);
else out[u].r = upd_outer(out[u].r, m, r, y, x);
return u;
}
int qry_inner(int node, int l, int r, int ql, int qr) const {
if (!node || qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return in[node].sum;
int m = (l + r) >> 1;
return qry_inner(in[node].l, l, m, ql, qr) +
qry_inner(in[node].r, m, r, ql, qr);
}
int qry_outer(int node, int l, int r, int qyl, int qyr, int qxl, int qxr) const {
if (!node || qyr <= l || r <= qyl) return 0;
if (qyl <= l && r <= qyr) {
return qry_inner(out[node].inner, 0, M, qxl, qxr);
}
int m = (l + r) >> 1;
return qry_outer(out[node].l, l, m, qyl, qyr, qxl, qxr) +
qry_outer(out[node].r, m, r, qyl, qyr, qxl, qxr);
}
void init(int coord_size, vector<Point> pts) {
M = coord_size;
in.clear();
out.clear();
vals.clear();
roots.clear();
in.push_back({});
out.push_back({});
sort(pts.begin(), pts.end(), [&](const Point& a, const Point& b) {
if (a.key != b.key) return a.key > b.key;
if (a.y != b.y) return a.y < b.y;
return a.x < b.x;
});
int cur = 0;
for (int i = 0; i < (int)pts.size();) {
int j = i;
while (j < (int)pts.size() && pts[j].key == pts[i].key) {
cur = upd_outer(cur, 0, M, pts[j].y, pts[j].x);
j++;
}
vals.push_back(pts[i].key);
roots.push_back(cur);
i = j;
}
}
int version_for_D(int D) const {
int lo = 0, hi = (int)vals.size() - 1, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (vals[mid] >= D) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}
// count active points with x in [xl, xr), y in [yl, yr)
int query(int D, int xl, int xr, int yl, int yr) const {
if (xl >= xr || yl >= yr) return 0;
int id = version_for_D(D);
if (id == -1) return 0;
return qry_outer(roots[id], 0, M, yl, yr, xl, xr);
}
};
int n;
vi h, ord, first_left, first_right;
int delta_left[100000], delta_right[100000];
SegTree st;
bitset<100000> seen_fwd, seen_rev;
int rpos(int i) { return 100000 - i - 1; }
PersistentRectCounter ds_mid, ds_left, ds_right;
void init(int N, vector<int> H) {
n = N;
h = H;
ord.resize(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int a, int b) { return h[a] < h[b]; });
first_left.assign(n, -1);
first_right.assign(n, n);
st = SegTree(n, h);
seen_fwd.reset();
seen_rev.reset();
for (int i : ord) {
int nxt = (int)seen_fwd._Find_next(i);
int rev = (int)seen_rev._Find_next(rpos(i));
int prv = (rev >= 100000 ? -1 : 100000 - 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]);
seen_fwd.set(i);
seen_rev.set(rpos(i));
}
vector<PersistentRectCounter::Point> p_mid, p_left, p_right;
p_mid.reserve(n);
p_left.reserve(n);
p_right.reserve(n);
for (int i = 0; i < n; i++) {
int x = first_left[i] + 1; // shift [-1..n-1] -> [0..n]
int y = first_right[i]; // [0..n]
p_mid.push_back({min(delta_left[i], delta_right[i]), x, y});
p_left.push_back({delta_right[i], x, y});
p_right.push_back({delta_left[i], x, y});
}
int M = n + 1;
ds_mid.init(M, p_mid);
ds_left.init(M, p_left);
ds_right.init(M, p_right);
}
int max_towers(int L, int R, int D) {
int ans = 1;
// first_left[i] >= L && first_right[i] <= R && min(dl,dr) >= D
// x = first_left+1 in [L+1, n+1), y = first_right in [0, R+1)
ans += ds_mid.query(D, L + 1, n + 1, 0, R + 1);
// first_left[i] < L && first_right[i] <= R && delta_right[i] >= D
// x in [0, L), after shift becomes [0, L+1), y in [0, R+1)
ans += ds_left.query(D, 0, L + 1, 0, R + 1);
// first_left[i] >= L && first_right[i] > R && delta_left[i] >= D
// x in [L+1, n+1), y in [R+1, n+1)
ans += ds_right.query(D, L + 1, n + 1, R + 1, n + 1);
return ans;
}
