#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 query_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(query_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(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));
}
};
struct Node {
Node *left = nullptr, *right = nullptr;
vi data;
Node() {}
Node(int x) : data(1, x) {}
Node(Node* lc, Node* rc) {
left = lc; right = rc;
if (!left) data = rc->data;
else if (!right) data = lc->data;
else {
int i = 0, j = 0;
while (i < lc->data.size() && j < rc->data.size()) {
if (lc->data[i] < rc->data[j]) data.push_back(lc->data[i++]);
else data.push_back(rc->data[j++]);
}
while (i < lc->data.size()) data.push_back(lc->data[i++]);
while (j < rc->data.size()) data.push_back(rc->data[j++]);
}
}
int query(int d) {
return data.end() - lower_bound(all(data), d);
}
};
struct PersistentMergeSortSegmentTree {
int n; vector<Node*> roots;
PersistentMergeSortSegmentTree(int n = 0) : n(n) {}
void update(int k, int v) {
Node* root = roots.empty() ? nullptr : roots.back();
roots.push_back(update(root, query_root, k, v));
}
Node* update(Node* cur, int i, int l, int r, int k, int v) {
if (!cur) cur = new Node();
if (!(l <= k && k < r)) return cur;
if (is_leaf) return new Node(v);
return new Node(update(cur->left, left_child, k, v), update(cur->right, right_child, k, v));
}
int query(int l, int r, int t1, int t2, int d) {
if (t2 < t1) return 0;
int a = query(roots[t2], query_root, l, r+1, d);
int b = t1 == 0 ? 0 : query(roots[t1-1], query_root, l, r+1, d);
return a-b;
}
int query(Node* cur, int i, int l, int r, int ql, int qr, int d) {
if (!cur) cur = new Node();
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return cur->query(d);
return query(cur->left, left_child, ql, qr, d) + query(cur->right, right_child, ql, qr, d);
}
};
const int MAXN = 100'000;
SegTree st;
PersistentMergeSortSegmentTree pst;
int n; vi h, idx, dl_idx, dl_ridx, dr_idx, dr_ridx;
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 ? 1e9 : st.query(prev, i+1) - h[i];
int right = nxt >= n ? 1e9 : 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));
pst = PersistentMergeSortSegmentTree(n);
dl_idx.assign(n, 0); dl_ridx.assign(n, 0);
dr_idx.assign(n, 0); dr_ridx.assign(n, 0);
iota(all(dl_idx), 0); sort(all(dl_idx), [&](int i, int j) {return first_left[i] == first_left[j] ? i < j : first_left[i] < first_left[j];});
iota(all(dr_idx), 0); sort(all(dr_idx), [&](int i, int j) {return first_right[i] == first_right[j] ? i < j : first_right[i] < first_right[j];});
for (int i = 0; i < n; i++) dl_ridx[dl_idx[i]] = dr_ridx[dr_idx[i]] = i;
for (int id = 0; id < n; id++) {
int i = dr_idx[id];
int pos = dl_ridx[i];
pst.update(pos, min(delta_left[i], delta_right[i]));
}
}
/*
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 when_less_l(int L) {
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi-lo)/2;
if (first_left[dl_idx[mid]] < L) lo = mid+1;
else hi = mid;
}
return lo-1;
}
int when_greater_r(int R) {
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi-lo)/2;
if (first_right[dr_idx[mid]] <= R) lo = mid+1;
else hi = mid;
}
return lo;
}
int max_towers(int L, int R, int D) {
int t = 0, lessl = when_less_l(L), morer = when_greater_r(R);
// cout << "L: " << L << " lessl: " << lessl << " fl[L]: " << first_left[dl_idx[lessl]] << " fl[L+1]: " << first_left[dl_idx[lessl+1]] << "\n";
// cout << "R: " << R << " morer: " << morer << " fr[R]: " << first_right[dr_idx[morer]] << " fr[R-1]: " << first_right[dr_idx[morer-1]] << "\n";
// 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();
// cout << "Querying the range: " << lessl+1 << "," << n << " in space, " << 0 << "," << morer-1 << " in time\n";
t += pst.query(lessl+1, n-1, 0, morer-1, D);
// cout << "Querying the range: " << 0 << "," << lessl+1 << " in space, " << 0 << "," << morer-1 << " in time\n";
t += pst.query(0, lessl, 0, morer-1, D);
// cout << "Querying the range: " << lessl+1 << "," << n << " in space, " << morer << "," << n-1 << " in time\n";
t += pst.query(lessl+1, n-1, morer, n-1, D);
// cout << "Querying the range: " << 0 << "," << lessl+1 << " in space, " << morer << "," << n-1 << " in time\n";
t += pst.query(0, lessl, morer, n-1, D);
// 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;
}
