1 条题解
信息
- ID
- 7080
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- (无)
- 递交数
- 45
- 已通过
- 15
- 上传者
十字斩是两条互相垂直、且与坐标轴成 45° 的直线,过询问点 (a,b):
释放十字斩会摧毁落在这两条直线上所有气球。
cnts[s]:值为 s=x−y 的气球总数cntt[t]:值为 t=x+y 的气球总数same:点位置上的气球,即两条直线交点根据容斥原理,总摧毁气球数:
ans=cntsa−b+cntta+b−same每个气球唯一对应一对,因此用 unordered_map<int,unordered_map<int,int>> cross 记录每对 (s,t) 的气球数量,查询时 cross[a-b][a+b] 就是 same 。