单行中的条件 设一行有 个棋子,最左和最右棋子的列为 。
列也满足相同条件。因此只需保存每行、每列的棋子数及首尾位置。
先统计横向吃子 对每一行,先加上可以横向吃子的空格数: 时为 , 时为 。仅在以下尚未计数的空区间内检查纵向条件:
忽略左端点大于右端点的空区间。这些区间都不包含棋子。
按行扫描与树状数组 在树状数组中,将当前行可以纵向吃子的列记为 ,其余记为 。棋子数至多为一的列始终为 ,至少为三的列始终为 。恰好两个棋子位于第 行的列,仅在 上方或 下方为 。
将两棋子的列初始化为 ,在处理第 行前改为 ,在处理第 行前改回 。若 ,则不需要第二个事件。至少三个棋子的列在棋子所在位置也存有 ,但查询区间不含棋子,因此不会误计。
将事件按行排序,从上到下扫描。先应用当前行的事件,再将最多两个剩余区间的和加入答案。这样每个可横向或纵向吃子的空格恰好被统计一次。
复杂度与数值范围 事件数不超过 。时间复杂度为 ,空间复杂度为 。因为 ,答案和棋盘面积的乘积应使用有符号 位整数。行列计数、树状数组区间和及下标均不超过 。生成器中的格子编号小于 ,也在 位范围内。
子任务 1 遍历所有格子,直接检查对应行列的条件,时间和空间均为 ,足以处理 。子任务 2 使用上述扫描算法。
Solution written by GPT6