CF1763

vp。

Div. 2.5。这场真是太蠢了。

B. Incinerate

先排序，存活的怪兽一定是一个后缀。预处理一下每次

然后发现直接暴力打的复杂度是 。然后就做完了。

C. Another Array Problem

发现对同一段区间做两次操作可以把它全部变成 。

于是对于 的情况可以把所有值变成最大值。

的情况特判一下就好了。

D. Valid Bitonic Permutations

既然有 解法，那为什么要放 ？？？

不妨设 。若不然，我们可以翻转整个序列，得到的方案数不变。

先考虑 的情况。

尝试枚举峰顶 的位置。显然 不能在 内。注意必须有上升和下降段， 不能取 或 。

无论 在何处， 所有数都在 内，方案数为 。

• ： 的数必须放在 ，这将会占去 个空位。剩余空位用来放 的数。贡献为 。
• ： 必须放 的数。 必须放 的数。贡献为 。

于是答案为

的情况相当于钦定了峰顶的位置，答案为 。

E. Node Pairs

这么蠢的题是怎么放到 的？？？

考虑对于一张图缩点双。显然两两可达的点只在点双内部。

设点双大小分别为 ，则第一问转化为 ，最小化 。

把大小为 的点双看作价值为 、重量为 的物品。有效物品只有根号级别，直接多重背包。

至于第二问？用脚指头都能想出来。把缩完的点双连成 ，除了必须双联通的点对，剩下的都可以单连通。

F. Edge Queries

没看明白限制条件有什么用。

路径上的非割边？建圆方树，方点点权为点双内边数（割边为 ），圆点点权为 。等价于静态查询路径权值和。