10.25 CSP-S模拟赛

你脑子呢？

确定的情况即选比 $a_i$ 小的，记 $a_i$ 的排名为 $rank_i$，则答案为 $\binom{rank_i - 1}{k - 1}$。

大力分讨。

无论什么情况都有一个直接走到的选项 $\operatorname{lcm}(x,y)$。

猜到跟质因数是有关系的。考虑如果中继节点多个一定不优，那么假设经过的中继节点为 $z$，则代价为 $z(x + y)$。如果说 $z$ 为 $x$ 的因数则 $x \to z$ 的代价即为 $x$，$z$ 是 $y$ 的因数同理。

根据以上结论来推。对于 $x,y$ 均为质数的数据点，

这种区间子区间直接算根本想不到，考虑传统艺能拆贡献。

考虑一个 $a_i$ 能产生贡献的区间，那么只要包含一个使得它不为前缀最大的数当前区间无效。

记 $x_i$ 表示满足 $j < i \land a_j > a_i$ 的第一个 $j$，那么包含 $x_i$ 的区间 $i$ 一定没贡献，那么可以得到：

前两个求和都可以直接前缀和，后面的偏序关系用四个树状数组分别维护。

复杂度 $O((n + q) \log n)$。

待补。