求助扫描线
  • 板块学术版
  • 楼主Flanksy
  • 当前回复13
  • 已保存回复13
  • 发布时间2023/2/10 14:17
  • 上次更新2023/10/24 01:15:31
查看原帖
求助扫描线
662295
Flanksy楼主2023/2/10 14:17

一个二维平面,nn 次操作后有 mm 次询问:

  • 给出两个整数点 (x1,y1)(x2,y2)(x_1,y_1)(x_2,y_2) 和一个值 xx,这两个点描述的矩形内部(包括边界)所有整数点值 +x+x

询问:

  • 给出两个整数点 (x1,y1)(x2,y2)(x_1,y_1)(x_2,y_2),求这两个点构成矩形内部(包括边界)所有整数点权值和。

想要一种线段树 + 扫描线的做法。

BDFS 无果,自己想了四种方法,实现时发现不正确。

求例题或正确思路,主要困惑的是如何拆解操作和询问使得一个询问的答案能够正确统计,如果不可做也请告知。

2023/2/10 14:17
加载中...