题意就是找到满足 形如 $a_l*a_r<=\max\limits_{i=l}^{r}a_i$ 的个数

题面的确挺简洁,然而想了好久也不知道怎么做,因为要考虑 $a_i,a_j,a_{max}$ 的其中两个

1. 如果枚举 $a_i$ 与 $a_{max}$ 那么需要找到 $max$ 到 $n$ 的所有小于等于 $\lfloor\frac{a_{max}}{a_i}\rfloor$ $a_j$ 的个数 或者我们枚举$a_i,a_j$ 看他们中的最大值是某满足

,而且还要一种数据结构(能查最值,或者能查大于/小于某个数的个数 ),在怎么都优化不下去了

然而这题分治的做法很巧妙,不过太难想出来了,我们把原序列看做一颗笛卡尔树,每一个节点变成了一段区间,依据笛卡尔树的结构,很显然我们找到了所有最值,此时我们把每个区间从最值部分划开,我们只要贪心地处理长度较小的那段区间,对每个数求小于等于 $\lfloor\frac{a_{max}}{a_i}\rfloor$ 的 $a_j$ 的数量就行了,不难发现每个点最多被计算 $\log_2n$ 次(本题是分治小的区间,如果这个点在小的区间统计次数超过了 $\log_2n$ 次,那大的区间已经超过了 $n$ 这显然是不成立的)

因此复杂度就分析出来了 $O(n\log^2n)$

但是你要注意的是虽然所有点贡献 $n\log n$ 次,但并不代表区间长度是这么多,如果你暴力求区间最大值的话只能拿到 $90$ 分,所以你得用 $st$ 表来做一做

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define ls(i) t[i].l
#define rs(i) t[i].r
#define int long long

using namespace std;

const int maxn=200010;

int a[maxn],b[maxn],n,rt[maxn],tot,ans,cnt;
int stb[maxn][18],l2[maxn];

struct segment_tree{ //板子部分,不多讲

struct tree{
int l,r,sum;
}t[maxn*30];

void change_tree(int &i,int looker,int l,int r,int x)
{
if(!i) i=++tot;
t[i]=t[looker];
t[i].sum++;
if(l==r) return ;
int mid=(l+r)>>1;
if(x<=mid) change_tree(ls(i)=++tot,ls(looker),l,mid,x);
else change_tree(rs(i)=++tot,rs(looker),mid+1,r,x);
}

int ask_sum_tree(int i,int l,int r,int x,int y)
{
if(y<x) return 0;
if(x>r||y<l) return 0;
int ans=0;
if(l>=x&&r<=y) return t[i].sum;
int mid=(l+r)>>1;
if(x<=mid) ans+=ask_sum_tree(ls(i),l,mid,x,y);
if(y>mid) ans+=ask_sum_tree(rs(i),mid+1,r,x,y);
return ans;
}

}st;

void getans(int l,int r)
{
if(l>r) return ;
if(l==r)
{
if(a[l]==1||a[l]==0) ans++;
return ;
}
int i,mmx;
int t1=stb[l][l2[r-l+1]];
int t2=stb[r-(1<<(l2[r-l+1]))+1][l2[r-l+1]];
if(a[t1]>=a[t2]) mmx=t1; else mmx=t2;
int sz1=(mmx-l+1),sz2=(r-mmx+1);
if(sz1<sz2)
{
for(i=l;i<=mmx;i++)
ans+=st.ask_sum_tree(rt[r],1,cnt,1,a[mmx]/a[i])-st.ask_sum_tree(rt[mmx-1],1,cnt,1,a[mmx]/a[i]);
}
else
{
for(i=mmx;i<=r;i++)
ans+=st.ask_sum_tree(rt[mmx],1,cnt,1,a[mmx]/a[i])-st.ask_sum_tree(rt[l-1],1,cnt,1,a[mmx]/a[i]);
}
getans(l,mmx-1);
getans(mmx+1,r);
}

signed main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n;
l2[0]=-1;
for(i=1;i<=n;i++) cin>>a[i],b[i]=a[i],stb[i][0]=i,l2[i]=l2[i>>1]+1; //预处理
for(j=1;j<=17;j++)
for(i=1;i<=n;i++)
stb[i][j]=(a[stb[i][j-1]]<a[stb[i+(1<<(j-1))][j-1]])?(stb[i+(1<<(j-1))][j-1]):(stb[i][j-1]);
cnt=1e9;
for(i=1;i<=n;i++) st.change_tree(rt[i],rt[i-1],1,cnt,a[i]);
getans(1,n);
cout<<ans<<endl;
return 0;
}