勇敢勇敢我的朋友（题解：P8912）

· · 题解

本题教会了我们，有时看似暴力的做法，实则优化一下就能跑进 1.00s 以内。

我们勇敢地去枚举 a_i,j,a_k 的值。又因为 a 是有序的，所以对此我们可以用两个数组 l,r 记录每个 a_i 的值对应的 i 的下标的区间范围（左端点和右端点）。例如当 a=\{2,3,3,4,5\} 时，我们的 l=\{1,1,2,4,5\},r=\{0,1,3,4,5\}，l_x>r_x 时代表 x 没有在 a 里出现过。我们可以发现 l_i=r_{i-1}+1，因此我们不必记录 l 数组。

然后我们设目前枚举到的 a_i \times j\times a_k=res。我们要求 i + a_j + k=res，而 a_j 是确定的，i,k 是不确定的。但是我们知道 i\in [l_{a_i},r_{a_i}]，所以移项可得 k\in [res-a_j-r_{a_i},res-a_j-l_{a_i}]。我们还知道 k\in [l_{a_k},r_{a_k}]，所以我们只需要求 [res-a_j-r_{a_i},res-a_j-l_{a_i}]\cup [l_{a_k},r_{a_k}] 所包含的数的数量就可以了。把每次枚举到的方案数加起来，就是总的方案数。

考虑优化。我们可以发现，设 m=a_n，则所有能造成贡献的 res 最大为 n+m+n（不理解请重新读题），所以我们可以在每一层循环时加上判断，当 res> n+m+n 跳出循环。看似这一个微小的操作没什么用，实则可以把原来 O(n^3)（因为 n,m 同阶，所以这里计算复杂度时不区别 n,m）的时间复杂度降至 O(n\log^2 n)。

分析一下，因为我们加上了判断，所以我们的 j 只枚举到了 \frac{n+n+m}{a_i}，平均起来大约是 O(\log n) 的，a_k 只枚举到了 \frac{n+n+m}{a_i j}，平均起来也大约是 O(\log n) 的。我们省去了大量的无意义的枚举，所以综合一下时间复杂度就是 O(n\log^2 n)，当我们再使用快读，我们就发现我们最慢的点才跑了 \text{931ms}。

上代码：

#include<bits/stdc++.h>
#define int long long//不开long long见祖宗
using namespace std;
const int N=1e6+5;
int r[N],a[N];
int n,m;
//
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
//上面的是快读
int query(int x,int y,int p,int q){//计算区间的并
    x=max(x,p);y=min(y,q);
    return max(y-x+1,0ll);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        r[a[i]]++;
    }
    m=a[n];
    for(int i=1;i<=m;i++){
        r[i]+=r[i-1];
    }
    int ans=0;
    for(int x=1;x<=m;x++){
        if(r[x-1]==r[x]) continue;//没出现过就跳过
        for(int j=1;j<=n;j++){
            if(x*j>n+n+m) break;
            for(int z=1;z<=m;z++){
                int res=x*j*z;
                if(res>n+n+m) break;
                if(r[z-1]==r[z]) continue;
                ans+=query(res-a[j]-r[x],res-a[j]-(r[x-1]+1),r[z-1]+1,r[z]);
            }
        }
    }
    cout<<ans;
    return 0;
}