这题的分治特征比较明显，但是按照传统的二分实现分治大概不可做。
更可做的是对于每个区间的最大值 \(O(n)\) 统计答案。
但是这样子复杂度无法保证是 \(O(n \log n)\) 的。
可以考虑把单层的复杂度优化到可以接受的范围内，这样即便分治的过程是一条链也只是多了一个 \(O(n)\) 而已。
首先，我们把取最大值的过程，用 ST 表优化为 \(O(1)\)。
然后，设当前区间 \([l,r]\) 最大值的位置为 \(mx\)，那么以 \(a_{mx}\) 为最大值的数对的答案相当于 \(\sum\limits_{i=l}^{mx} \sum\limits_{j=mx+1}^{r} [a_j \le \dfrac{a_{mx}}{a_i}]\)，两个 \(\sum\) 的范围交换也一样。
其中 \([X]\) 表示如果 \(X\) 成立即为 \(1\) 否则为 \(0\)。
发现后面这个 \(\sum\) 可以用主席树来做，单次 \(O(\log n)\)。
现在最大的问题是确定前面这个 \(\sum\) 的取值范围。
非常显然地，我们可以启发式地取两边长度较小的一边来枚举。
这样的话，对于 \(a\) 单调的数据，开始提到的那种分治是 \(O(n^2)\) 的，这个算法反而可以做到 \(O(n \log n)\)。
而能够使那种分治的复杂度为 \(O(n \log n)\) 的数据反而是这个算法的上界，即 \(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
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));
}