题解：AT_arc123_e [ARC123E] Training

· · 题解

我们令 f(i) 为 A 在第 i 天的等级，g(i) 为 B 的。

首先考虑一下没有天数上限怎么做。

我们考虑直接计算 \sum \limits_{L} \sum \limits_i [f(i)=L][g(i)=L]。

可以发现其对应到数轴上就分别是一个长度为 B_x 与 B_y 的区间。这两个区间一个每次会移动 B_x 位一个会移动 B_y 位。不妨设 B_x < B_y，并且令 \Delta = B_y-B_x。则 x 到 y 的移动会经历这四个阶段（令两个区间分别为 [l_x,r_x] 与 [l_y,r_y]），每个阶段中的每次移动都会给答案产生贡献：

  3. l_y \le l_x \le r_x \le r_y$：每次的贡献值为 $B_x

需要注意的是，这五个阶段可能并不都出现。当没有天数上限的时候，直接对着算即可。

现在有了天数上限，则可以算出 n 是在哪个阶段的哪个点，单独处理那一个等级即可。

时间复杂度 O(T)。