#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
const int INF = 2e9;
struct Node {
int cnt;
Node *l, *r;
Node(int cnt, Node* l, Node* r) : cnt(cnt), l(l), r(r) {}
Node() : cnt(0), l(nullptr), r(nullptr) {}
};
class Persistent {
int offset;
vector <Node*> root;
Node* NIL;
public:
Node* update(Node* x, int lo, int hi, int pos) {
if (pos < lo || pos >= hi)
return x;
if (hi - lo == 1)
return new Node(x -> cnt + 1, NIL, NIL);
int mid = lo + (hi - lo) / 2;
Node* lft = update(x -> l, lo, mid, pos);
Node* rig = update(x -> r, mid, hi, pos);
return new Node(lft -> cnt + rig -> cnt, lft, rig);
}
Persistent(vector <int> vals) {
NIL = new Node();
NIL -> l = NIL -> r = NIL;
root.push_back(NIL);
for (auto &it : vals)
it = min(it, INF / 2);
int mx = *max_element(vals.begin(), vals.end());
for (offset = 1; offset < mx; offset *= 2);
for (int i = 1; i < vals.size(); i++)
root.push_back(update(root.back(), 0, offset, vals[i]));
}
Persistent() {}
int query(Node* x, int lo, int hi, int from, int to) const {
if (lo >= to || hi <= from)
return 0;
if (lo >= from && hi <= to)
return x -> cnt;
int mid = lo + (hi - lo) / 2;
return query(x -> l, lo, mid, from, to) + query(x -> r, mid, hi, from, to);
}
int query(Node* x, int to) const {
return query(x, 0, offset, 0, to);
}
int get(int from, int to, int val) const {
return query(root[to - 1], val) - query(root[from - 1], val);
}
};
int N, lg;
vector <int> H;
vector <int> ex;
vector <int> lb, ub;
vector <vector <int>> mini;
vector <vector <int>> lft, rig;
Persistent count_lb, count_ub;
int query(int from, int to) {
if (from >= to)
return INF;
int tmp = ex[to - from];
return min(mini[from][tmp], mini[to - (1 << tmp)][tmp]);
}
void init_sparse() {
mini.resize(N + 1, vector <int> (lg + 1));
for (int i = 1; i <= N; i++)
mini[i][0] = H[i];
for (int j = 1; j <= lg; j++)
for (int i = 1; i <= N; i++)
mini[i][j] = min(mini[i][j - 1], i + (1 << j - 1) > N ? INF : mini[i + (1 << j - 1)][j - 1]);
ex.resize(N + 1);
for (int i = 2; i <= N; i++)
ex[i] = ex[i / 2] + 1;
}
void init_lft_rig() {
lft.resize(N + 2, vector <int> (lg + 1));
rig.resize(N + 2, vector <int> (lg + 1));
stack <int> s;
s.push(0);
for (int i = 1; i <= N; i++) {
while (H[s.top()] < H[i])
s.pop();
lft[i][0] = s.top();
s.push(i);
}
s = stack <int> ();
s.push(N + 1);
for (int i = N; i; i--) {
while (H[s.top()] < H[i])
s.pop();
rig[i][0] = s.top();
s.push(i);
}
rig[N + 1] = vector <int> (lg + 1, N + 1);
for (int j = 1; j <= lg; j++)
for (int i = 1; i <= N; i++) {
lft[i][j] = lft[lft[i][j - 1]][j - 1];
rig[i][j] = rig[rig[i][j - 1]][j - 1];
}
}
void init_lb_ub() {
lb.resize(N + 1);
ub.resize(N + 1);
for (int i = 1; i <= N; i++) {
int tmp = query(lft[i][0] + 1, rig[i][0]);
lb[i] = H[i] - tmp;
ub[i] = min(H[lft[i][0]], H[rig[i][0]]) - tmp;
}
count_lb = Persistent(lb);
count_ub = Persistent(ub);
}
void init(int n, vector <int> h) {
N = n;
H.resize(N + 2);
H[0] = H[N + 1] = INF;
for (int i = 1; i <= N; i++)
H[i] = h[i - 1];
while (1 << lg < N)
lg++;
init_sparse();
init_lft_rig();
init_lb_ub();
}
int max_towers(int l, int r, int d) {
l += 1;
r += 1;
int smaller_lb = count_lb.get(l, r + 1, d);
int smaller_ub = count_ub.get(l, r + 1, d);
auto binary = [&](int x, const function <bool(int)> &check, const vector <vector <int>> &anc) -> pair <int, int> {
if (!check(x))
return {0, x};
int res = 0;
for (int i = lg; i >= 0; i--)
if (check(anc[x][i])) {
x = anc[x][i];
res |= 1 << i;
}
return {res + 1, anc[x][0]};
};
auto lb_lft_plus = [&](int node) {
return rig[node][0] <= r && H[node] - query(l, rig[node][0]) < d;
};
auto lb_rig_plus = [&](int node) {
return lft[node][0] >= l && H[node] - query(lft[node][0] + 1, r + 1) < d;
};
auto lb_lft_minus = [&](int node) {
return rig[node][0] <= r && lb[node] < d;
};
auto lb_rig_minus = [&](int node) {
return lft[node][0] >= l && lb[node] < d;
};
auto ub_lft_plus = [&](int node) {
return rig[node][0] <= r && H[rig[node][0]] - query(l, rig[node][0]) < d;
};
auto ub_rig_plus = [&](int node) {
return lft[node][0] >= l && H[lft[node][0]] - query(lft[node][0] + 1, r + 1) < d;
};
auto ub_lft_minus = [&](int node) {
return rig[node][0] <= r && ub[node] < d;
};
auto ub_rig_minus = [&](int node) {
return lft[node][0] >= l && ub[node] < d;
};
auto check_mx = [&](int node) {
return rig[node][0] <= r;
};
smaller_lb += binary(l, lb_lft_plus, rig).first + binary(r, lb_rig_plus, lft).first - binary(l, lb_lft_minus, rig).first - binary(r, lb_rig_minus, lft).first;
smaller_ub += binary(l, ub_lft_plus, rig).first + binary(r, ub_rig_plus, lft).first - binary(l, ub_lft_minus, rig).first - binary(r, ub_rig_minus, lft).first;
int arg_max = binary(l, check_mx, rig).second;
smaller_lb -= lb[arg_max] < d;
smaller_lb += H[arg_max] - query(l, r + 1) < d;
smaller_ub -= ub[arg_max] < d;
return smaller_lb - smaller_ub;
}
