#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 vvi = vector<vi>;
/*
greedy left to right (sorted order) bitset idea
(2 incompatible towers that make valid subsets of the same size theres no reason not to use the smaller one)
*/
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 root 0, 0, n
int n; vi st, arr;
SegTree() {}
SegTree(int n, vi arr) : n(n), arr(arr), st(4*n, INT_MIN) {build(root);}
int build(int i, int l, int r) {
if (is_leaf) return st[i] = arr[l];
return st[i] = max(build(left_child), build(right_child));
}
int query(int ql, int qr) {return query(root, ql, qr);}
int query(int i, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return INT_MIN;
if (ql <= l && r <= qr) return st[i];
return max(query(left_child, ql, qr), query(right_child, ql, qr));
}
};
const int MAXN = 100'000;
SegTree st;
int n; vi h, idx;
int first_left[MAXN], first_right[MAXN], delta_left[MAXN], delta_right[MAXN];
bitset<100'000> f, r;
int rpos(int i) {return r.size() - i - 1;}
vi c1, c2, c3, c4;
void init(int N, vi H) {
n = N; h = H; idx.assign(n, 0); iota(all(idx), 0);
sort(all(idx), [&](int i, int j) {return h[i] < h[j];});
st = SegTree(n, H);
for (auto i : idx) {
int prev = rpos(r._Find_next(rpos(i)));
int nxt = f._Find_next(i);
first_left[i] = prev; first_right[i] = min(n, nxt);
int left = prev < 0 ? INT_MAX : st.query(prev, i+1) - h[i];
int right = nxt >= n ? INT_MAX : st.query(i, nxt+1) - h[i];
delta_left[i] = left; delta_right[i] = right;
f.set(i), r.set(rpos(i));
if (first_left[i] >= 0 && first_right[i] <= n-1) c1.push_back(min(delta_left[i], delta_right[i]));
else if (first_left[i] < 0 && first_right[i] <= n-1) c2.push_back(delta_right[i]);
else if (first_left[i] >= 0 && first_right[i] > n-1) c3.push_back(delta_left[i]);
else c4.push_back(i);
}
sort(all(c1)); sort(all(c2)); sort(all(c3));
}
/*
how much structure can be exploited ?!?
sort by 1 axis
persistent segment tree / line sweep over another axis
range queries over a third axis
(a) sort by first_left[i], have a pst over first_right[i], then query how many values >= D ?!? (sounds like persistent merge sort, but 2gb limit ig)
(b)
*/
int max_towers(int L, int R, int D) {
int t = 0;
t += c1.end() - lower_bound(all(c1), D);
t += c2.end() - lower_bound(all(c2), D);
t += c3.end() - lower_bound(all(c3), D);
t += c4.size();
// for (int i = L; i <= R; i++) {
// if (first_left[i] >= L && first_right[i] <= R && min(delta_left[i], delta_right[i]) >= D) t++;
// if (first_left[i] < L && first_right[i] <= R && delta_right[i] >= D) t++;
// if (first_left[i] >= L && first_right[i] > R && delta_left[i] >= D) t++;
// if (first_left[i] < L && first_right[i] > R) t++;
// // if ((first_left[i] < L || delta_left[i] >= D) && (first_right[i] > R || delta_right[i] >= D)) t++;
// }
return t;
}
