Uoj#40. 【清华集训2014】卡常数
题意:
- 三维空间中有$n$个点。
- 每次询问距离给出点为某个距离的点是什么或者修改一个点的坐标。
- 操作参数加密,所有坐标随机生成。
- $n,m\le 65536$。
题解:
- 首先加密函数考虑$f(x)=ax-b\sin(x)$。
- $f’(x)=a-b\cos(x)$。
- 而$a>b\ge0$,所以$f(x)$单调递增。
- 所以我们可以二分来解密。
- 听说标算是个很厉害的利用加密特点的做法。
- 但我并没有看懂。。
- 但是这题还是可以直接上$\rm KD-Tree$。
- 因为坐标是随机生成,所以什么根据方差来选择哪一维就不必要了,直接按顺序选择三维就可以了。
- 查询大概就是:
- 维护出每个子空间中所有点的$x,y,z$的最大最小值。
- 设置最近函数为:
- 对于每一维,如果坐标在最大最小之间,设为$0$。
- 否则设置为与其中较近的距离。
- 设置最远函数为:
- 每一维距离取与最大最小值差的较大值。
- 然后对于每个其中可能存在答案的子空间递归查找。
- 修改大概就是直接暴力插入点,删除原先点并维护其相关信息。
- 因为数据随机,所以不需要替罪羊树暴力重构的方法。
- 复杂度$O((n+m)\sqrt{n})$。
代码:
1 |
|