JOI Final 2021

loj3469. 「JOI 2021 Final」雪球

发现 \(i\) 的答案只和相邻的两个数有关，且两边是独立的，不妨假设 \(a_i=0\)，\(a_{i+1}=d\)。那么假设第 \(j\) 次操作 \(a_{i+1}\) 到达的最小位置是 \(d-mn_j\)，\(a_i\) 到达最大位置是 \(mx_j\)，那么第 \(j\) 次操作 \(i\) 拓宽的区间是 \((mx_{j-1},mx_j]\)，\(a_{i+1}\) 已经拓宽的区间是 \([d-mn_{j-1},d]\)，那么 \(i\) 的答案会加上 \(\max(0,\min(d-mn_{j-1},mx_j)-mx_{j-1})\)。考虑维护出 \(a_{i+1}-a_i=d\) 的答案 \(f(d)\)，那么操作是区间加一次函数，差分一下维护即可。

loj3470. 「JOI 2021 Final」集体照

相当于交换使得 \(a_i+i\) 不降，玩一下可以发现合法序列一定是若干个公差为 \(-1\) 且值域连续的等差数列拼接而成，考虑每次填一段，只需要算这个情况下排列的逆序对数，二维前缀和一下就好了。

loj3471. 「JOI 2021 Final」机器人

因为这个颜色的限制很宽松，所以可以发现一条边总能交换到一个没有用过的颜色（菊花除外，但是菊花的答案是显然的），所以一条边交换的花费一定为 \(p_i\)，不交换的花费是 \(sum_{u,c}-p\)。不过发现边的贡献和前一条边有一定的关系，可以发现只有前一条边和当前边颜色相同，且当前边不变，前一条边变的时候，贡献才会减少一个数。我们建立一个虚点表示钦定进入这种状态，然后直接跑 Dijkstra 即可。

有一些存疑的地方是改变其它的边可能会影响到路径上其它点的临边，这样权值可能会改变。不过可以发现直接走临边相当于会跳过一段路径，所以这么做是不优的。于是上述做法无后效性。

loj3472. 「JOI 2021 Final」地牢 3

原题意是不好做的，对着原题意硬做顶多得到一个基于维护凸包的单次线性做法。所以考虑转化题意。

把第 \(i\) 层地牢看做数轴上位置为 \(\sum_{j<i}a_j\) 的点（不妨写作 \(c_i\)），那么原问题等价于第 \(i\) 个点可以覆盖位置为 \([c_i,c_i+u)\) 的任意位置，覆盖一个位置的代价是 \(b_i\)，求覆盖 \([c_{s},c_t)\) 中所有点的代价最小值。这是容易理解的，因为我们可以把加能量的过程看做是不断拓展能到达的位置的过程，而拓展位置容易理解为覆盖。

那么贪心做法就比较显然了：对于一个位置 \(p\)，找到 \((p-u,p]\) 中代价最小的点，然后加进去即可。

考虑怎么做原问题。因为 \(u\) 会改变，所以直接维护贪心是十分不方便的，考虑进一步刻画。我们对于 \(i\)，找到 \(i\) 的前驱 \(\text{pre}_i\) 和后继 \(\text{nxt}_i\)，满足 \(b_{\text{pre}_i}\leq b_i,b_{\text{nxt}_i}<b_i\)，且分别为所有位置中最大 / 最小的（不存在分别设为 \(-\infty\) 和 \(\infty\)）。那么对于位置 \(p\)，假设它被 \(i\) 覆盖，那么需要满足：\(p\geq c_i,p\geq c_{\text{pre}_i}+u,i<c_i+u,p<c_{\text{nxt}_i}\)。说明当 \(c_{\text{pre}_i}+u<c_{\text{nxt}_i}\) 的时候，\(p\) 的区间是 \([\max(c_i,c_{\text{pre}_i}+u),\min(c_i+u,c_{\text{nxt}_i}))\)，其长度是段数为 \(\mathcal{O}(1)\)，次数不超过 \(1\) 的关于 \(u\) 的分段函数，所以可以尝试开一个线段树，维护每个 \(u\) 的贡献，支持区间加一次函数和单点求值。

考虑加上区间的限制，发现右端点并不影响，可以使用差分等技巧解决（稍后提及）。那么我们扫描线枚举左端点 \(l\)，分别维护每个点的贡献。注意当 \(\text{pre}_i<l\) 的时候，\(\text{pre}_i\) 视为不存在，所以需要在 \(l=i\) 的时候加入一次 \(i\)，\(l=\text{pre}_i\) 的时候删除前面的 \(i\) 并重新加入一次带有 \(\text{pre}_i\) 限制的 \(i\)。考虑怎么解决右端点的限制，我们找到覆盖 \(c_r\) 的点，处理出它的区间 \([lp,rp]\)，然后减去这段区间在 \([c_r,\infty)\) 处的贡献；之后，我们再找到覆盖 \(rp+1\) 的点 \(p\)，补上 \([a_p,rp]\) 的贡献，并减去 \(l=p\) 时 \(u\) 的答案（相当于减去了后面一整段区间的贡献）。这样我们就得到了区间 \([l,r]\) 的答案。

code