[题解] P4755 Beautiful Pair

P4755 Beautiful Pair

给你一个长度为 \(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;
}