自动搬运

查看原文

来自洛谷，原作者为

	noip 对你说再见

搬运于2025-08-24 21:52:45，当前版本为作者最后更新于2017-05-30 23:01:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

特技卡常数题

其实这个题考的不是常数优化

是膜法

这样的

你们都会+1-1rmq吧？

不会有关系，因为你听不懂后面我要说啥

但是其实也没关系，因为我都没写过

仔细想想+1-1rmq，那个四毛子的用途？

可以得到这样一个改良算法

分块，大小设为x

预处理每个块两端到块内每个点的前缀max和后缀max

预处理块间ST表

然后查询的时候

比如说我查l，r，这两个分别在块a，b中

然后就是查块a，b之间的rmq，以及l在a块的后缀max和r在b块的前缀max

块大小为logn的时候，这个算法是O( 1 )的

但是 要真的是这样的

那发明+1-1rmq的人岂不是naive？

肯定不是

那个算法有一个问题

就是查询的两个点都在同一个块中会出偏差

但是 块大小logn啊

所以复杂度最坏是nlogn

然而我可以微调块大小让你根本没法卡

然后这个题数据随机是不是

设块大小为x

则两个端点同一个块概率为1/x，代价为O( x )

所以可以让x = sqrt( n )因为预处理ST表挺慢的

这样就可以解决了

期望下O( n )的rmq

而且不用笛卡尔树什么的，常数超级小哦~

这个大概是一个不错的rmq算法，跑得又快，常数又小，还好写

重点是没人卡你，卡还不一定卡的住，还要冒着被暴力AC的风险

最后放上183炸鱼图