luogu4755Beautiful_Pair

标签 ：分治 + RMQ + 树状数组

这题看起来很分治，所以考虑分治。

一般的分治是在中间分开，可以发现这道题在中间分开并没有很好的性质。

于是 果断放弃 我们发现如果在最大值处分开会有很好的性质。因为在最大值处分开，所以左边的点和右边的点之间的最大值确定。(最大值可以用 \(ST表\) 求)

考虑枚举左端点，那么右端点要满足的条件是 $a_r \times a_l \leq a_{mid} $, 即 \(a_r \leq \frac{a_{mid}}{a_l}\) 。所有满足条件的右端点的个数就是区间 \([mid,r]\) 中值比 \(\frac{a_{mid}}{a_l}\) 小的点的数量，这个可以直接用主席树求，也可以离线下来用树状数组求。

发现从最大值处分开的话复杂度并不正确，是 \(O(n^2\lg n)\) .

可以运用启发式思想，在枚举端点时，不一定必须枚举左端点，可以在 \(mid\) 两边长度更小的那个区间中枚举端点，这样复杂度就是\(O(n \lg^2n)\) 的啦，证明如下。

对于每个点，每当它被枚举到一次，它所在的分治区间会缩小至少一半，所有对于每个点，他最多被枚举 \(O(\lg n)\) 次，所以树状数组最多会接受到 \(O(n \lg n)\) 次询问，复杂度自然就是 \(O(n \lg^2 n)\)

Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long

using namespace std;

const int N = 1e5 + 10;
int n;

struct QUE
{
	int x, v, op;
	bool operator < (const QUE b) const
	{
		return x < b.x;
	}
}q[3 * N * 20];
int tot;

int a[N], b[4 * N * 20], cnt;
int st[N][30], d[N][30], lg[N];
ll ans;
int val[N * 6 * 20];

int lowbit(int x)
{
	return x & (-x);
}

void add(int x, int v)
{
	for (int i = x; i <= 20 * n; i += lowbit(i))
	{
		val[i] += v;
	}
}

int query(int x)
{
	int res = 0;
	for (int i = x; i; i -= lowbit(i)) res += val[i];
	return res;
}

int find(int l, int r)
{
	int k = lg[r - l + 1];
	if (st[l][k] > st[r - (1 << k) + 1][k])
	{
		return d[l][k];
	}
	else return d[r - (1 << k) + 1][k];
}

void dfs(int l, int r)
{
	if (l == r) return ans += (a[l] == 1), void();
	if (l > r) return ;
	int mx = find(l, r);
	if (r - mx < mx - l)
	{
		for (int i = mx; i <= r; ++i)
		{
			q[++tot] = (QUE){mx, a[mx] / a[i], 1};
			q[++tot] = (QUE){l - 1, a[mx] / a[i], -1};
		}
	}
	else
	{
		for (int i = l; i <= mx; ++i)
		{
			q[++tot] = (QUE){r, a[mx] / a[i], 1};
			q[++tot] = (QUE){mx - 1, a[mx] / a[i], -1};
		}
	}
	dfs(l, mx - 1);
	dfs(mx + 1, r);
}

int main()
{
	scanf("%d", &n);
	lg[1] = 0;
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &a[i]);
		st[i][0] = a[i], d[i][0] = i;
	}
	for (int i = 2; i <= n; ++i)
	{
		lg[i] = lg[i / 2] + 1;
	}
	for (int k = 1; k <= lg[n]; ++k)
	{
		for (int i = 1; i <= n - (1 << k) + 1; ++i)
		{
			if (st[i][k - 1] > st[i + (1 << (k - 1))][k - 1])
			{
				st[i][k] = st[i][k - 1];
				d[i][k] = d[i][k - 1];
			}
			else 
			{
				st[i][k] = st[i + (1 << (k - 1))][k - 1];
				d[i][k] = d[i + (1 << (k - 1))][k - 1];
			}
		}
	}
	dfs(1, n);
	for (int i = 1; i <= n; ++i)
	{
		b[++cnt] = a[i];
	}
	for (int i = 1; i <= tot; ++i)
	{
		b[++cnt] = q[i].v;
	}
	sort(b + 1, b + cnt + 1);
	for (int i = 1; i <= n; ++i)
	{
		a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
	}
	for (int i = 1; i <= tot; ++i)
	{
		q[i].v = lower_bound(b + 1, b + cnt + 1, q[i].v) - b;
	}
	sort(q + 1, q + tot + 1);
	int u = 0;
	for (int i = 1; i <= tot; ++i)
	{
		while (u < q[i].x)
		{
			++u;
			add(a[u], 1);
		}
		ans += 1ll * q[i].op * query(q[i].v);
	}
	cout << ans << endl;
	return 0;
}

注意数组的大小, 有些数组大小级别是 \(O(n\lg n)\)