题解 P3793 【由乃救爷爷】

特技卡常数题 其实这个题考的不是常数优化 是膜法 这样的 你们都会+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炸鱼图