思路:
CF1712 E1/E2 LCM Sum (easy/hard version)
二维数点/二维偏序:
- 二维前缀和+扫描线+树状数组+ 离线处理
- 应用: 求 Q次询问, L-R内 x-y的 点的数量(矩形内点的数量)
- 直接用二维前缀和, 时间复杂度, 一定不允许, 发现 二维前缀和是由 4个 到1,1 的矩阵相互操作得到
- 于是把点按照 x轴排序, 再利用 扫描线,扫x轴, 利用树状数组, 存下 y 轴点的数量.
LCM Sum (CF E ) (正男则反, 二维数点/二维偏序, 大胆的抽象化简数学式子, 打表找规律)
发布时间 2023-09-06 09:58:26作者: VxiaohuanV