给你一个长度为 \(n\) 的序列 \(a\)，求有多少个区间 \([l, r]\) 满足 \(a_l \cdot a_r \le \max_{i = l}^r a_i\)。
\(n \le 10^5, a_i \le 10^9\)。
首先按最大值位置分治。记当前分治区间为 \([l, r]\)，分治中心为 \(mid\)。那么我们现在要做的就是统计跨分治中心的二元组的答案。
不妨设 \(mid - l < r - mid\)。枚举 \([l, mid]\) 中的每个数 \(a_i\)，这样问题就转化为了 \([mid, r]\) 中有多少个数小于等于 \(\frac{a_{mid}}{a_i}\)，这个可以离线下来扫描线解决。
时间复杂度 \(O(n \log^2 n)\)。
constexpr int MAXN = 1e5 + 9, MAXLG = 17;
int n, a[MAXN];
vector<int> num, upd[MAXN];
pii st[MAXLG][MAXN];
vector<pair<int, int> > qry[MAXN];
ll ans = 0;
struct Fenwick {
int n; vector<int> c;
Fenwick(): n(0) { return; }
Fenwick(int _n): n(_n), c(_n + 1) { return; }
void Update(int x, int k) {
for (; x <= n; x += x & -x) c[x] += k;
return;
}
int Query(int x) {
ll ans = 0;
for (; x; x ^= x & -x) ans += c[x];
return ans;
}
int Query(int l, int r) {
return Query(r) - Query(l - 1);
}
};
pii Query(int l, int r) {
int k = __lg(r - l + 1);
return max(st[k][l], st[k][r - (1 << k) + 1]);
}
void Solve(int l, int r) {
if (l > r) return;
int mid = Query(l, r).sec;
if (mid - l < r - mid) {
for (int i = l; i <= mid; i ++) {
int x = num[a[mid]] / num[a[i]];
if (x < num.front()) continue;
x = upper_bound(num.begin(), num.end(), x) - num.begin() - 1;
qry[x].emplace_back(mid, r);
}
} else {
for (int i = mid; i <= r; i ++) {
int x = num[a[mid]] / num[a[i]];
if (x < num.front()) continue;
x = upper_bound(num.begin(), num.end(), x) - num.begin() - 1;
qry[x].emplace_back(l, mid);
}
}
Solve(l, mid - 1), Solve(mid + 1, r);
return;
}
void slv() {
n = Read<int>();
for (int i = 1; i <= n; i ++) num.emplace_back(a[i] = Read<int>());
sort(num.begin(), num.end()), num.erase(unique(num.begin(), num.end()), num.end());
for (int i = 1; i <= n; i ++) a[i] = lower_bound(num.begin(), num.end(), a[i]) - num.begin();
for (int i = 1; i <= n; i ++) upd[a[i]].emplace_back(i);
for (int i = 1; i <= n; i ++) st[0][i] = {a[i], i};
for (int i = 1; i <= __lg(n); i ++) for (int j = 1; j + (1 << i) - 1 <= n; j ++)
st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
Solve(1, n);
Fenwick tr(n);
for (int i = 0; i < num.size(); i ++) {
for (auto j : upd[i]) tr.Update(j, 1);
for (auto [l, r] : qry[i]) ans += tr.Query(l, r);
}
Write(ans, '\n');
return;
}