#include "towers.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using ari2 = array<int, 2>; using ari3 = array<int, 3>; using arl2 = array<ll, 2>; using arl3 = array<ll, 3>; template <class T> using vt = vector<T>; #define all(x) begin(x), end(x) #define size(x) (int((x).size())) #define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d)) #define FOR(a,b,c) REP(a,b,c,1) #define ROF(a,b,c) REP(a,b,c,-1) constexpr int mxN = 100005; int N, H[mxN]; vt<int> d_vals; struct ST { ari2 st[mxN << 1]; void update(int i, const int v) { st[i + N] = {v, i}; for (i += N; i >>= 1; ) st[i] = max(st[i << 1], st[i << 1 | 1]); } int query(int l, int r) { int ret = 0; for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) ret = max(ret, st[l++][0]); if (r & 1) ret = max(ret, st[--r][0]); } return ret; } int query2(int l, int r) { ari2 ret = {INT_MIN, -1}; for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) ret = max(ret, st[l++]); if (r & 1) ret = max(ret, st[--r]); } return ret[1]; } } max_st, l_dif_st, r_dif_st, min_st; struct Node { int cnt, lm, rm; Node *lft, *rht; Node(const int c = 0, const int l = N, const int r = -1) : cnt(c), lm(l), rm(r), lft(nullptr), rht(nullptr) {} Node(Node *l, Node *r) : cnt(l->cnt + r->cnt), lm(min(l->lm, r->lm)), rm(max(l->rm, r->rm)), lft(l), rht(r) {} Node(Node *n) : cnt(n->cnt), lm(n->lm), rm(n->rm), lft(n->lft), rht(n->rht) {} } *pst[mxN]; Node *build(const int tl = 0, const int tr = N - 1) { if (tl == tr) return new Node(); const int tm = tl + tr >> 1; return new Node(build(tl, tm), build(tm + 1, tr)); } Node *update(Node *n, const int p, const int tl = 0, const int tr = N - 1) { if (tl == tr) return new Node(1, p, p); const int tm = tl + tr >> 1; if (p <= tm) return new Node(update(n->lft, p, tl, tm), n->rht); return new Node(n->lft, update(n->rht, p, tm + 1, tr)); } ari3 query(Node *n, const int ql, const int qr, const int tl = 0, const int tr = N - 1) { if (tl > qr || tr < ql) return {0, N, -1}; if (ql <= tl && tr <= qr) return {n->cnt, n->lm, n->rm}; const int tm = tl + tr >> 1; const ari3 l = query(n->lft, ql, qr, tl, tm), r = query(n->rht, ql, qr, tm + 1, tr); return {l[0] + r[0], min(l[1], r[1]), max(l[2], r[2])}; } int d_ind(const int v) { return lower_bound(all(d_vals), v) - d_vals.begin(); } int max_towers(const int l, const int r, const int d) { auto [ans, L, R] = query(pst[d_ind(d)], l, r); if (R < 0) ans = 1, L = R = min_st.query2(l, r); return ans + (r_dif_st.query(l, L - 1) >= d) + (l_dif_st.query(R + 1, r) >= d); } void init(const int _N, const vt<int> _H) { N = _N; FOR(i, 0, N - 1) H[i] = _H[i]; vt<int> L(N), R(N), stk; FOR(i, 0, N - 1) { while (size(stk) && H[stk.back()] > H[i]) stk.pop_back(); L[i] = size(stk) ? stk.back() : -1; stk.push_back(i); } stk.clear(); ROF(i, N - 1, 0) { while (size(stk) && H[stk.back()] > H[i]) stk.pop_back(); R[i] = size(stk) ? stk.back() : N; stk.push_back(i); } FOR(i, 0, N - 1) max_st.update(i, H[i]), min_st.update(i, -H[i]); vt<int> dif(N); FOR(i, 0, N - 1) { const int lv = max_st.query(max(0, L[i]), i) - H[i]; const int rv = max_st.query(i, min(N - 1, R[i])) - H[i]; d_vals.push_back(dif[i] = min(lv, rv)); l_dif_st.update(i, lv); r_dif_st.update(i, rv); } sort(all(d_vals)); d_vals.erase(unique(all(d_vals)), d_vals.end()); vt<vt<int>> sweep(size(d_vals)); FOR(i, 0, N - 1) sweep[d_ind(dif[i])].push_back(i); pst[size(d_vals)] = build(); ROF(i, size(d_vals) - 1, 0) { pst[i] = new Node(pst[i + 1]); for (const auto &j : sweep[i]) pst[i] = update(pst[i], j); } }