D 又是一年毕业季

F 自爆机器人

结论：一段长度为的区间，它的子区间长度设子区间长度为

那么不同的数量不会超过个

，不同的 都取尽可能小，设为，有$1 +2 + \dots + m = n\$

可得，

思路：

将路径拆解成两部分——从到的必要路线，在任意两个墙壁来回走的路线

如果的话显然不可能炸到怪物

除去到的必要路线需要花费的时间外，还剩的时间可以在两个墙壁来回走

将两个墙壁来回走的路线拆解成只在相邻墙壁来回走的路线可以变成

对于设，设每两个墙壁间走次

可得

使用完全背包求解，的种类不会超过，时间复杂度可通过结论证明为

G 大鱼吃小鱼

发现题目给的时间段是左闭右开联想到差分操作

对时间段离散化，用差分表示在时刻加入第条鱼，第时刻消失第条鱼，用前缀和维护第时刻有哪些鱼

枚举时刻，求第时刻开吃的话最大能到多大的体重。对体重离散化，然后用树状数组维护离散化后体重为的鱼的实际总重量

维护操作：

• 第条鱼加入时有（是离散化后体重为的鱼原本的体重）
• 第条鱼消失时有

设当前体重为（同样被离散化），查询在时刻第一条体重大于的鱼的离散化体重，然后吃掉在这之间的所有鱼。如不存在体重大于的鱼，那么可以把这一时刻所有的鱼都吃掉

如果吃完后体重的话，那么继续迭代操作

如果吃完后体重，已经不可能吃掉这条鱼了，退出迭代，此时是时刻能到达的最大体重

因为每次可以吃掉体重自身的鱼后，都相当于至少对之前的体重，所以体重增长速度是指数级别的，最多只会遇到次比自身体重大的鱼

查询第时刻第一条体重大于操作——用multiset维护当前有哪些体重的鱼(体重为实际体重)，用内置upperbound函数求出体重大于的鱼

时间复杂度