关于矩形散点加矩形查询
  • 板块学术版
  • 楼主DPair
  • 当前回复6
  • 已保存回复6
  • 发布时间2021/3/3 21:23
  • 上次更新2023/11/5 02:29:32
查看原帖
关于矩形散点加矩形查询
66511
DPair楼主2021/3/3 21:23

就是说一开始给你 nn 个二维平面上的散点,每一个散点有一个权值初始为 00 ,每一次操作要么是给一个矩形内的所有散点权值加上一个值,要么是查询一个矩形内所有散点的权值和。

显然区间逆序对的离线版本可以转化为这个问题,但是似乎无法实现(我试过 KDTree 但是超级慢)。

所以这个东西是已经基本上被认为不可做了,还是说有什么我没想到的高妙做法?好像说区间逆序对可以转化为另一个什么很毒瘤的问题所以没法做来着的((

我对这一块并不是很了解,大佬勿喷。

特指某半夜出没的lxl

2021/3/3 21:23
加载中...