10.25 CSP-S模拟赛
xAlec
·
·
个人记录
T1
你脑子呢？
确定的情况即选比 a_i 小的，记 a_i 的排名为 rank_i，则答案为 \binom{rank_i - 1}{k - 1}。
T2
大力分讨。
无论什么情况都有一个直接走到的选项 \operatorname{lcm}(x,y)。
猜到跟质因数是有关系的。考虑如果中继节点多个一定不优，那么假设经过的中继节点为 z，则代价为 z(x + y)。如果说 z 为 x 的因数则 x \to z 的代价即为 x，z 是 y 的因数同理。
根据以上结论来推。对于 x,y 均为质数的数据点，
T3
这种区间子区间直接算根本想不到，考虑传统艺能拆贡献。
考虑一个 a_i 能产生贡献的区间，那么只要包含一个使得它不为前缀最大的数当前区间无效。
记 x_i 表示满足 j < i \land a_j > a_i 的第一个 j，那么包含 x_i 的区间 i 一定没贡献，那么可以得到：
\begin{aligned}
g(l,r) &= \sum\limits_{i=l}^{r}{(i - max(l - 1, x_i))(r - i + 1)}
\\
&= \sum\limits_{i=l}^{r}{(x_i - i)(r + 1)} - \sum\limits_{i=l}^{r}{i \times (x_i - i)} - \sum\limits_{i=l}^{r}{[x_i < l](l - x_I - 1)(r - i + 1)}
\\
&= \sum\limits_{i=l}^{r}{(x_i - i)(r + 1)} - \sum\limits_{i=l}^{r}{i \times (x_i - i)} - \sum\limits_{i=l}^{r}{[x_i < l]((l - 1)(r + 1) - i(l - 1) - x_i(r + 1)
+ x_i \times i)}
\end{aligned}
前两个求和都可以直接前缀和，后面的偏序关系用四个树状数组分别维护。
复杂度 O((n + q) \log n)。
T4
待补。