1 条题解

  • 1
    @ 2026-9-26 22:53:45

    十字斩是两条互相垂直、且与坐标轴成 45°45° 的直线,过询问点 (a,b)(a,b):

    • 直线 1:y−x=b−ay−x=b−a (正对角线,记 s=x−ys=x−y )
    • 直线 2:y+x=b+ay+x=b+a (斜率为 −1-1,反对角线,记 t=x+yt=x+y )

    释放十字斩会摧毁落在这两条直线上所有气球。

    • cnts[s]:值为 s=x−ys=x−y 的气球总数
    • cntt[t]:值为 t=x+yt=x+y 的气球总数
    • same:点位置上的气球,即两条直线交点

    根据容斥原理,总摧毁气球数:

    ans=cntsa−b+cntta+b−sameans=cnts_{a-b}+cntt_{a+b}−same

    每个气球唯一对应一对,因此用 unordered_map<int,unordered_map<int,int>> cross 记录每对 (s,t)(s,t) 的气球数量,查询时 cross[a-b][a+b] 就是 same 。

    信息

    ID
    7080
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    (无)
    递交数
    45
    已通过
    15
    上传者