洛谷。
题意
显然。
分析
首先考虑到分治，那么问题就在于如何维护经过某个结点的方案数。
利用从中间结点向两端的前缀后缀最大值，接下来我们对左端点的每一个结点考虑连向右侧的方案数。
考虑分类讨论，令左端点为 \(i\)，右端点为 \(j\)。
假如 \(mx_i> mx_j\)，那么我们整个区间的最大值就是 \(mx_i\)。如此，化一下式子 \(mx_i\ge a_i\times a_j\)，\(a_j\le \frac{mx_i}{a_i}\)。
假如 \(mx_i<=mx_j\)，那么我们的区间最大值就是 \(mx_j\)。同上，\(a_i\le \frac{mx_j}{a_j}\)。
我们看到这两个式子，我们肯定会考虑使用树状数组来维护这个个数，但是随之而来的又有一个问题，我们的两侧式子有可能是浮点数，那又应当如何解决呢？
可以发现，我们的两个式子只会有一边是浮点数，且另一侧是原数字，因此，我们可以将我们的浮点数向下取整的同时在原数字基础下离散化即可。
具体的细节都是分治的常规操作，就不细讲了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
inline int read() {
int x;
scanf("%lld",&x);
return x;
}
int n, m, a[N],ans,mx[N],num[N],cnt_num,c[N],b[N];
struct Bit {
int c[N+2];
inline int lowbit(int x) {
return x&-x;
}
inline void change(int x,int y) {
++x;
for(int i=x; i<=N; i+=lowbit(i)) c[i]+=y;
}
inline int query(int x) {
++x;
int tot=0;
for(int i=x; i; i-=lowbit(i)) tot+=c[i];
return tot;
}
inline int query(int l,int r) {
return query(r)-query(l-1);
}
} bit,bit2;
inline int lsh(int x) {
return upper_bound(num,num+cnt_num+1,x)-num-1;
}
inline int lsh2(int i) {
return lsh(mx[i]/a[i]);
}
inline void solve(int L,int R) {
if(L>R) return ;
if(L==R) return void(ans+=a[L]==1);
int mid=L+R>>1;
mx[mid]=a[mid],mx[mid+1]=a[mid+1];
for(int i=mid+2; i<=R; ++i) mx[i]=max(mx[i-1],a[i]);
for(int i=mid-1; i>=L; --i) mx[i]=max(mx[i+1],a[i]);
for(int i=mid+1; i<=R; ++i) c[i]=lsh2(i);
for(int i=mid+1; i<=R; ++i) bit2.change(c[i],1);
int r=mid;
for(int i=mid; i>=L; --i) {
while(r<R&&mx[r+1]<mx[i]) {
++r;
bit.change(b[r],1);
bit2.change(c[r],-1);
}
ans+=bit.query(lsh(mx[i]/a[i]))+bit2.query(b[i],N);
}
for(int i=mid+1; i<=r; ++i) bit.change(b[i],-1);
for(int i=r+1; i<=R; ++i) bit2.change(c[i],-1);
solve(L,mid),solve(mid+1,R);
}
signed main() {
n=read();
for(int i=1; i<=n; ++i) num[i]=a[i]=read();
sort(num+1,num+n+1);
cnt_num=unique(num+1,num+n+1)-num-1;
for(int i=1; i<=n; ++i) b[i]=lower_bound(num+1,num+cnt_num+1,a[i])-num;
solve(1,n);
cout<<ans;
return 0;
}