[ABC356E] Max/Min 讲解

· · 题解

题目考察：前缀和，二分，调和级数。
题目简述：
给你 \{a_n\}，求：

\sum_{i=1}^{n-1}\sum_{j=i+1}^n\lfloor\frac{\max(a_i,a_j)}{\min(a_i,a_j)}\rfloor

数据范围：

我们将式子变形得：

\sum_{i=1}^{n-1}\sum_{j=i+1}^n\lfloor\frac{\max(a_i,a_j)}{\min(a_i,a_j)}\rfloor=\sum_{i=1}^n\sum_{j=1}^n[a_j\ge a_i\land i\ne j]\times\lfloor\frac{a_j}{a_i}\rfloor

我们再将 \{a_n\} 升序排序变为：

\sum_{i=1}^n\sum_{j=1}^n[a_j\ge a_i\land i\ne j]\times\lfloor\frac{a_j}{a_i}\rfloor=\sum_{i=1}^{n-1}\sum_{j=i+1}^n\lfloor\frac{a_j}{a_i}\rfloor

那么我们考虑如何快速求 \displaystyle \sum_{i=1}^{n-1}\sum_{j=i+1}^n\lfloor\frac{a_j}{a_i}\rfloor，我们将 \{a_n\} 分块，将 \displaystyle\lfloor\frac{a_j}{a_i}\rfloor 相同的 a_j 分在一组。设 \displaystyle k=\lfloor\frac{a_j}{a_i}\rfloor，则这些数一定是区间 [ka_i,(k+1)a_i) 之间的数，那么我们可以用二分或者前缀和来维护个数，我用的是二分（设 a_l\ge ka_i>a_{l-1}，a_{r+1}\ge(k+1)a_i>a_r，l,r 为满足上述条件的数），这组数的贡献就是 k(r-l+1)。
这样的做法显然可以被一半 1，一半不是 1，使复杂度退化为 O(n^2)，所以我们要特判相同数字。

证明时间复杂度合理：
这样运行次数最多为 \displaystyle\sum_{i=1}^n\lfloor\frac{n-i}{i}\rfloor，下面证明复杂度：

\begin{aligned}\sum_{i=1}^n\lfloor\frac{n-i}{i}\rfloor&\le\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\\&\le\sum_{i=1}^n\lfloor\frac{n}{2^{\lfloor\log_2i\rfloor}}\rfloor\\&=\sum_{i=1}^{\lfloor\log_2n\rfloor}2^i\times\lfloor\frac{n}{2^i}\rfloor\\&\le\sum_{i=1}^{\lfloor\log_2n\rfloor}2^i\times\frac{n}{2^i}\\&=\sum_{i=1}^{\lfloor\log_2n\rfloor}n\\&\le n\log_2n\end{aligned}

故复杂度小于 n\log_2n，实际约为 n\ln n。

代码： 

#include<bits/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=y;++i) 
#define per(i,x,y) for(reg int i=x;i>=y;--i)
#define endl '\n'
#define INF LLONG_MAX
using namespace std;
const int N=2e5+5;
int n,a[N],ans;
signed main(){
    fst;
    cin>>n;
    rep(i,1,n) cin>>a[i];
    sort(a+1,a+n+1);
    rep(i,1,n){
        reg int l=i+1,tot=a[l]/a[i],sum=0;
        while(l<=n){
            reg int r=lower_bound(a+l,a+n+1,a[i]*(tot+1))-a-1;
            sum+=(r-l+1)*tot;
            l=r+1;
            tot=a[l]/a[i];
        }
        ans+=sum;
        while(a[i+1]==a[i]){
            --sum;
            ans+=sum;
            ++i;
        }
    }
    cout<<ans;
    return 0;
}