传统异能，我又来光速更新 JOI Final 的题解惹。

A - Intercastellar

不知道咋说，直接模拟记连续段长度就好。

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

B - Self Study

先对每个 \(a_i\) 和 \(b_i\) 取 \(\max\)。

考虑二分答案，考虑对于一门课来说：它要么全部课上满还达不到 \(mid\)，需要另外翘几次来补；要么若干次上课后达到要求了，那么就多了几次翘课。于是我们比较需要翘课的次数和多出来翘课的次数的大小就能 check 当前的 \(mid\) 了。

复杂度 \(O(n\log 10^{18})\)。

C - Let's Win the Election

考虑我们的决策肯定是先按 \(B_i\) 大小在几个州赢得协作者，然后再在剩下的几个州里面赢满选票。

为了下文描述方便，令 \(S\) 表示赢得协作者的州的集合，\(T\) 表示赢得选票的州的集合。

那么考虑按 \(B_i\) 从小到大排序，考虑对于一个前缀 \(i\) 来说，如果 \(i\) 是编号最大的赢得协作者的州，那么对于每个 \(j\ (j<i)\)，要么 \(j\in S\)，要么 \(j\in T\)。

证明的话就考虑如果前面有一个州 \(k\) 既没赢得协作者，也没赢得选票，那么可以在 \(S\) 中删去 \(i\)，再加入 \(k\)，这样调整显然答案会变优。

于是我们可以枚举 \(S\) 的大小，然后对于每个后缀 \(i\) 先求出要赢 \(j\) 张选票的最小代价，对于每个前缀 \(i\) 去 DP 一下选 \(|S|\) 个赢得协作者的州和 \(i-|S|\) 个赢得选票的州的代价，然后合并即可。

时间复杂度 \(O(n^3)\)。

D - Railway Trip 2

对于一个起点来说，走若干步能到的点显然是个区间，倍增加速整个过程即可。

E - Sandcastle 2

先假设 \(n\le m\)（不满足就把整个矩形旋转下就行，答案显然不变）。

考虑怎么 check 一个子矩形是否合法。

考虑当前在 \((i,j)\) 接下来肯定会走到周围格子里小于 \((i,j)\) 并且最大的位置，否则肯定走不完整个自矩形。

于是我们考虑，每个点 \((i,j)\) 向它周围的比它小但是最大的格子连一条有向边。一个子矩形合法，当且仅当这个这样连边后的图是一条有向链，稍微转化一下合法的条件就是：

  1. 不存在入度大于 \(1\) 的点。
  2. 恰好存在一个入度等于 \(0\) 的点。

注意到一个点的入度大小仅和子矩形的四条边界与其的距离和 \(2\) 取较小值有关。

考虑枚举矩形的上下边界，再枚举下边界的过程中，维护一个 \(cnt[i][j][k][0/2]\) 表示左边界和第 \(i\) 列的距离和 \(2\) 取 \(\min\) 后是 \(j\)，右边界和第 \(i\) 列的距离和 \(2\) 取 \(\min\) 后是 \(k\) 时，度数为 \(0/2\) 的点的个数。

每次下边界移动，只有当前行和前一行的出度会改变，重新计算下这两行对于另外点的入度的贡献，同时再更新下 \(cnt\) 就行。

统计答案考虑枚举右边界，根据 \(cnt\) 维护两个 bitset，第 \(i\) 位表示 \(i\) 作为左边界是否满足条件 1/2，两个取并就行得到当前的贡献。

时间复杂度 \(O(HW\min(HW)+\frac{(HW)^2}{\omega})\)。