rt，用的是建完笛卡尔树后启发式合并的做法，统计答案在两个 $\text{vector}$ 跑小的(tmp)一个循环，对于大的(ans)二分。时间复杂度大概是 $\Theta(n\log^2n)$?

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,a[N],lc[N],rc[N],S[N],tp;
int rt,L[N],R[N],id[N],idx,sz[N],son[N];
vector<int>E[N];
void dfs(int u){
    L[u]=++idx;
    id[idx]=u;
    for(auto v:E[u]){
        dfs(v);
        if(sz[son[u]]<sz[v]){
            son[u]=v;
        }
    }
    R[u]=idx;
    sz[u]=R[u]-L[u]+1;
}
ll res;
int sum1ans,sum1tmp;
vector<int>ans,tmp;
void dfs2(int u,bool keep){
    for(auto v:E[u]){
        if(v==son[u]){
            continue;
        }
        dfs2(v,0);
    }
    if(son[u]){
        dfs2(son[u],1);
        tmp.clear();
        sum1tmp=0;
        for(int i=L[u]+1;i<L[son[u]];i++){
            tmp.push_back(a[id[i]]);
            if(a[id[i]]==1){
                ++sum1tmp;
            }
        }
        for(int i=R[son[u]]+1;i<=R[u];i++){
            tmp.push_back(a[id[i]]);
            if(a[id[i]]==1){
                ++sum1tmp;
            }
        }
        sort(ans.begin(),ans.end());
        sort(tmp.begin(),tmp.end());
        auto Find=[&](int x){
            int l=0,r=ans.size()-1,res=-1;
            while(l<=r){
                int mid=(l+r)/2;
                if(ans[mid]<=x){
                    res=mid;
                    l=mid+1;
                }else{
                    r=mid-1;
                }
            }
            return res+1;
        };
        res=res+sum1ans;
        res=res+sum1tmp;
        for(auto x:tmp){
            res=res+Find(a[u]/x);
        }
        sum1ans=sum1ans+sum1tmp;
        for(auto x:tmp){
            ans.push_back(x);
        }
    }
    if(a[u]==1){
        ++sum1ans;
        ++res;
    }
    ans.push_back(a[u]);
    if(!keep){
        sum1ans=0;
        ans.clear();
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        int x=0;
        while(tp&&a[i]>=a[S[tp]]){
            x=S[tp--];
        }
        if(S[tp]){
            rc[S[tp]]=i;
        }
        if(x){
            lc[i]=x;
        }
        S[++tp]=i;
    }
    rt=S[1];
    for(int i=1;i<=n;i++){
        if(lc[i]){
            E[i].push_back(lc[i]);
        }
        if(rc[i]){
            E[i].push_back(rc[i]);
        }
    }
    dfs(rt);
    dfs2(rt,0);
    printf("%lld\n",res);
    return 0;
}