DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

炮

返回题目

题解

单行中的条件 设一行有 ttt 个棋子,最左和最右棋子的列为 L,RL,RL,R。

  • 当 t≤1t\leq1t≤1 时,无法横向吃子。
  • 当 t=2t=2t=2 时,仅 LLL 左侧或 RRR 右侧的空格可以吃子。两个棋子之间的空格在任一方向上都没有两个棋子。
  • 当 t≥3t\geq3t≥3 时,每个空格都可以吃子,因为左右至少一侧有两个或更多棋子。

列也满足相同条件。因此只需保存每行、每列的棋子数及首尾位置。

先统计横向吃子 对每一行,先加上可以横向吃子的空格数:t=2t=2t=2 时为 (L−1)+(M−R)(L-1)+(M-R)(L−1)+(M−R),t≥3t\geq3t 时为 。仅在以下尚未计数的空区间内检查纵向条件:

  • t=0t=0t=0:[1,M][1,M][1,M]。
  • t=1t=1t=1:[1,L−1][1,L-1][1, 和 。

忽略左端点大于右端点的空区间。这些区间都不包含棋子。

按行扫描与树状数组 在树状数组中,将当前行可以纵向吃子的列记为 111,其余记为 000。棋子数至多为一的列始终为 000,至少为三的列始终为 111。恰好两个棋子位于第 U,DU,DU,D 行的列,仅在 UUU 上方或 下方为 。

将两棋子的列初始化为 111,在处理第 UUU 行前改为 000,在处理第 D+1D+1D+1 行前改回 111。若 D=ND=ND,则不需要第二个事件。至少三个棋子的列在棋子所在位置也存有 ,但查询区间不含棋子,因此不会误计。

将事件按行排序,从上到下扫描。先应用当前行的事件,再将最多两个剩余区间的和加入答案。这样每个可横向或纵向吃子的空格恰好被统计一次。

复杂度与数值范围 事件数不超过 KKK。时间复杂度为 O(N+M+Klog⁡(K+1)+Klog⁡(M+1)+Nlog⁡(M+1))O(N+M+K\log(K+1)+K\log(M+1)+N\log(M+1))O(N+M+Klog(K+1),空间复杂度为 。因为 ,答案和棋盘面积的乘积应使用有符号 位整数。行列计数、树状数组区间和及下标均不超过 。生成器中的格子编号小于 ,也在 位范围内。

子任务 1 遍历所有格子,直接检查对应行列的条件,时间和空间均为 O(NM+N+M+K)O(NM+N+M+K)O(NM+N+M+K),足以处理 NM≤10 000NM\leq10\,000NM≤10000。子任务 2 使用上述扫描算法。

Solution written by GPT6

≥
3
M−tM-tM−t
L
−
1]
[L+1,M][L+1,M][L+1,M]
  • t=2t=2t=2:[L+1,R−1][L+1,R-1][L+1,R−1]。
  • t≥3t\geq3t≥3:没有剩余区间。
  • DD
    D
    111
    =
    N
    111
    +
    Klog(M+
    1)+
    Nlog(M+
    1))
    O(N+M+K)O(N+M+K)O(N+M+K)
    0≤answer≤NM−K<2.5⋅10110\leq\mathrm{answer}\leq NM-K<2.5\cdot10^{11}0≤answer≤NM−K<2.5⋅1011
    646464
    500 000500\,000500000
    NMNMNM
    646464