[RC-06] ijk 题解

pikiuk · 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) 求解。