网站首页
编程语言
数据库
系统相关
其他分享
编程问答
大块
2024-07-16
O(1) 修改的 RMQ
前天uq里有人问这个。单点修改区间\(min\),能不能做到修改\(O(1)\)查询\(O(\sqrtn)\)。后来和@critno私下讨论了一会,得到了\(O(1)\)修改\(O(n^{\epsilon})\)查询的算法,并进行了简化版的实现。算法本质是操作序列分块。先考虑一个朴素算法。原序列不动,跑RMQ。
2024-06-17
ABC353F 分讨
回来补补题。分析:我先考虑\(k\)很大的时候,大块和大块间的移动,我们不得不尽量避免小块:我们容易发现这样时是最优的,可以发现就是在斜着走,也就是典型的切比雪夫距离。斜着走一次需要经过两条边,所以花费是两倍的切比雪夫距离。要是起点和终点不在大块上呢?首先考虑它们不在同一