自动搬运

查看原文

来自洛谷，原作者为

	pikiuk “Back like I never left!”

搬运于2025-08-24 22:43:40，当前版本为作者最后更新于2022-12-25 08:58:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

注意到 $i+a_j+k$ 有上界 $m\leq 3\times 10^6$，因此我们可以大胆枚举左边的 $a_i,j,a_k$ 的值，这部分的复杂度不超过 $m\log^2 m$。

之后我们相当于要求出有多少个 $i,k$ 满足 $i+j=a_i\times j\times a_k - a_j$，又因为序列有单调性，$i,j$ 的取值范围都是一段区间，这个很容易用桶记一下求出具体的区间。

现在相当于求解 $x+y=z$ 且 $x\in [l_1,r_1]$，$y\in[l_2,r_2]$ 的解的个数，不难 $\mathcal{O}(1)$ 求解。