【VP 记录】EDU132

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-04 22:32:15

记录

AB 10min 顺利过了，C 卡一整场，写了个假做法，最后看 D 结果切了。

VP 后发现 C 是简单题补了，E 蓝启发式合并，F 紫没读题，不补了。

简单模拟，略过不表。

预处理每一位向右和向左的代价，分别做前缀和和后缀和，每次查询只拿出一段区间的代价即可。

VP 时想到了要转化为前缀和数组非负，由此可以想到从左向右依次处理，维护目前前缀值 ${cnt}$ 和未确定的位置数 ${res}$，容易想到 $cnt$ 为零时问号必填左括号，否则不合法。

由此扩展，若 $res+cnt=1$，也即这一位之前所有未填的全部为左括号恰能填满，则这一位也必须填左括号。

最后若 $res=\left|cnt\right|$，也即所有未处理的位置都是同种括号，就只有一种填法，否则有多种填法。

显然起点和终点的横纵坐标必须分别模 $k$ 同余，否则无法每次走 $k$ 格走到。

由于被封锁的是靠近底部的一部分，因此考虑尽可能走高处的格，发现在起点所在列尽可能向上走，再横着走到终点列，最后向下走到终点的走法受到的限制最小。

这样就需要保证起点列和终点列之间在横着走的这一行没有被封锁，也即求起点列和终点列之间的最值，用 ST 表或线段树解决即可。