洛谷 4755.Beautiful Pair

这题的分治特征比较明显,但是按照传统的二分实现分治大概不可做。
更可做的是对于每个区间的最大值 O(n)O(n) 统计答案。
但是这样子复杂度无法保证是 O(nlogn)O(n \log n) 的。

可以考虑把单层的复杂度优化到可以接受的范围内,这样即便分治的过程是一条链也只是多了一个 O(n)O(n) 而已。

首先,我们把取最大值的过程,用 ST 表优化为 O(1)O(1)
然后,设当前区间 [l,r][l,r] 最大值的位置为 mxmx,那么以 amxa_{mx} 为最大值的数对的答案相当于 i=lmxj=mx+1r[ajamxai]\sum\limits_{i=l}^{mx} \sum\limits_{j=mx+1}^{r} [a_j \le \dfrac{a_{mx}}{a_i}],两个 \sum 的范围交换也一样。
其中 [X][X] 表示如果 XX 成立即为 11 否则为 00
发现后面这个 \sum 可以用主席树来做,单次 O(logn)O(\log n)
现在最大的问题是确定前面这个 \sum 的取值范围。

非常显然地,我们可以启发式地取两边长度较小的一边来枚举。
这样的话,对于 aa 单调的数据,开始提到的那种分治是 O(n2)O(n^2) 的,这个算法反而可以做到 O(nlogn)O(n \log n)
而能够使那种分治的复杂度为 O(nlogn)O(n \log n) 的数据反而是这个算法的上界,即 O(nlog2n)O(n \log^2 n)

壮哉我大主席树!

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
const int N = 1e5;
const int A = 1e9;
const int LG = 20;
using namespace std;
int n,a[N + 5];
int st[N + 5][LG + 5],lg2[N + 5];
struct node
{
int cnt;
int ls,rs;
} seg[(N << 5) + 10];
int rt[N + 5];
void insert(int x,int k,int &p,int tl,int tr)
{
static int tot = 0;
seg[++tot] = seg[p],p = tot,++seg[p].cnt;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
if(x <= mid)
insert(x,k,seg[p].ls,tl,mid);
else
insert(x,k,seg[p].rs,mid + 1,tr);
}
int query(int l,int r,int p,int tl,int tr)
{
if(!p || (l <= tl && tr <= r))
return seg[p].cnt;
int mid = tl + tr >> 1;
int ret = 0;
if(l <= mid)
ret += query(l,r,seg[p].ls,tl,mid);
if(r > mid)
ret += query(l,r,seg[p].rs,mid + 1,tr);
return ret;
}
long long solve(int l,int r)
{
if(l > r)
return 0;
if(l == r)
return a[l] <= 1;
int mx,lg = lg2[r - l + 1];
if(a[st[l][lg]] >= a[st[r - (1 << lg) + 1][lg]])
mx = st[l][lg];
else
mx = st[r - (1 << lg) + 1][lg];
long long ret = solve(l,mx - 1) + solve(mx + 1,r);
if(mx - l < r - mx)
for(register int i = l;i <= mx;++i)
ret += query(1,a[mx] / a[i],rt[r],1,A) - query(1,a[mx] / a[i],rt[mx - 1],1,A);
else
for(register int i = r;i >= mx;--i)
ret += query(1,a[mx] / a[i],rt[mx],1,A) - query(1,a[mx] / a[i],rt[l - 1],1,A);
return ret;
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),st[i][0] = i;
for(register int i = 2;i <= n;++i)
lg2[i] = lg2[i / 2] + 1;
for(register int i = 1;i <= LG;++i)
for(register int j = 1;j + (1 << i) - 1 <= n;++j)
if(a[st[j][i - 1]] >= a[st[j + (1 << i - 1)][i - 1]])
st[j][i] = st[j][i - 1];
else
st[j][i] = st[j + (1 << i - 1)][i - 1];
for(register int i = 1;i <= n;++i)
insert(a[i],1,rt[i] = rt[i - 1],1,A);
printf("%lld\n",solve(1,n));
}