自动搬运

查看原文

来自洛谷，原作者为

	FlierKing **

搬运于2025-08-24 22:03:17，当前版本为作者最后更新于2018-07-14 23:34:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们考虑用分治的思想来解决这个问题。假设我们在计算区间$[l,r]$数对的数量，其中这个区间的最左端的最大值的位置为$mx$，那么我们可以先考虑处理$[l,mx-1]$区间数对的数量和$[mx+1,r]$区间数对的数量。

对于一个区间$[l,r]$，当我们确定了$a_l$时，只需要求$[mx+1,r]$中数字不大于$\frac {a_{mx}}{a_l}$的即是以$l$为左端点答案的对数（因为我们分区间是以最左端的最大值区分的），当确定了$a_r$时同理。此时我们可以枚举小的区间，然后确定另一边要查询的区间以及查询的值，记录下后离线查询。

可以证明，所有查询的区间数量不超过$n\ log\ n$个。考虑当进行一次长度为$len$的枚举时，那么此时被分开的区间长度必然大于$2\times len$，那么对于任意一个数字，它被枚举的次数必然不超过$log\ n$，每被枚举一次会形成一个询问区间，所以询问区间不超过$n\ log\ n$个。

考虑如果选定一个端点，那么可行的右端点的数量可以用树状数组查询。（查询 $[l,r]$ 中小于 $x$ 的数字数量可以用 $[1,r]$ 中小于 $x$ 的数字数量减去 $[1,l-1]$ 中小于 $x$ 的数字数量）

询问一个区间$[l,r]$小于等于$x$的数字数量可以用树状数组解决，用$[1,r]$中的小于等于$x$的数字数量减去$[1,l-1]$中的小于等于$x$的数字数量即为答案。

#include <bits/stdc++.h> 
#define ll long long
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define MAXN 500005
using namespace std;
    int n,en,r,len;
    int a[MAXN],L[MAXN],R[MAXN],b[MAXN];
    pr s[MAXN];
    vector <int> g[MAXN];
    ll ans;
    ll tr[MAXN];
int inline read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline int abs(int x){return x>=0?x:-x;}
inline int find_ind(int x){return x>=b[n]?n:upper_bound(b+1,b+len+1,x)-b-1;}
inline int lowbit(int x){return x&-x;}
ll query(int x)
{
    ll res=0;
    while (x)
    {
        res+=tr[x];
        x-=lowbit(x);
    }
    return res;
}
void update(int x,int v)
{
    while (x<=n)
    {
        tr[x]+=v;
        x+=lowbit(x);
    }
}
int main()
{
    n=read();
    for (int i=1;i<=n;i++)
        b[i]=a[i]=read();
    for (int i=1;i<=n;i++)
    {
        while (en&&s[en].fi<a[i]) en--;
        L[i]=en?s[en].se+1:1;
        s[++en]=make_pair(a[i],i);
    }
    en=0;
    for (int i=n;i;i--)
    {
        while (en&&s[en].fi<=a[i]) en--;
        R[i]=en?s[en].se-1:n;
        s[++en]=make_pair(a[i],i); 
    }
    for (int i=1;i<=n;i++)
    {
        if (i-L[i]<=R[i]-i) 
        {
            g[i-1].pb(-1);
            g[R[i]].pb(1);
            for (int j=L[i];j<i;j++)
            {
                g[i-1].pb(-a[i]/a[j]);
                g[R[i]].pb(a[i]/a[j]);
            }
        }
        else
        {
            g[L[i]-1].pb(-1);
            g[i].pb(1);
            for (int j=i+1;j<=R[i];j++)
            {
                g[L[i]-1].pb(-a[i]/a[j]);
                g[i].pb(a[i]/a[j]);
            }
        }
    }
    sort(b+1,b+n+1);
    len=unique(b+1,b+n+1)-b-1;
    for (int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+len+1,a[i])-b;
    for (int i=1;i<=n;i++)
    {
        update(a[i],1);
        int to=g[i].size();
        for (int j=0;j<to;j++)
        {
            r=find_ind(abs(g[i][j]));
            g[i][j]<0?ans-=query(r):ans+=query(r);
        }
    }
    cout<<ans;
    return 0;
}