CF1998 div2 & abc366

1 CF

1.1 B

被诈骗了。我们的构造要向“每个区间只有 1 个数不一样考虑”。

1.2 C

比较难。但是出的好。

注意到如果我们不删除中位数这个位置的数，那么那个数是一定的。

所以我们可以把 \(k\) 加到最大的可以加的数上，统计答案就在这个数，然后二分算中位数即可。

其它策略？

我们可不可以使得中位数变大一点？

此时我们就询问 \(a_n\)，然后通过操作来使得中位数最大即可。

操作也是很好想的，如果对 \(a\) 排序然后每次二分实现的话复杂度就是 \(O(n\log V)\) 的。

1.3 D

被诈骗？？？

确实，今天 15 分钟切了。

如果你提前求出从 1 到达每个点的最少时间，你发现不好做，因为你要限制的区间是有约束的。

换句话说，假设 A 从 \(s\) 开始走到 \(t\)，你知道 \(dp_t\)，但是 \(dp_t\) 可能由 \([s,t)\) 的数转移过来，就没办法了。

解决方法也很好想，顺序扫描，每次统计从 \(i\) 出发的边所造成的贡献。对于边 \(i\to to\)，此时只考虑了 \([1,i)\) 的边，所以对于 \([i+1,to)\) 的点，这时的 dp 值完全是不限制的、正确的；所以我们计算一下影响区间就好了，打一个数组差分。

1.4 E

1.4.1 E1

wzy 赛时过了,说笛卡尔树，我接着做了差不多 20 分钟过了。

建出树来，发现如果 \(sum_l\) 大于 \(a_x\) 的话，那么 \(l\) 就一定可以替代 \(x\)。\(r\) 同理。

但是有一个前提，就是到祖先的路径上的点都是可以的。

所以两次 dfs 即可。

严谨的证明你考虑每次操作是 upd 和删除，那此时 \(x\) 和 \(l,r\) 所表示的数在 \(S\) 里面就一定是相邻的。

其实我交上去发现过了也觉得很不可思议。

1.4.2 E2

还不会。

2 ABC

2.1 E

之前做过类似，直接把 \(x\) 和 \(y\) 分开处理。

绝对值的形式也很经典。

2.2 F

贪心还是很经典。

不会证明，但是都是选 2 个数来确定排序方式。

排序完了做 dp 就行。

2.3 G

异或高斯消元，不会。