题解 P3793 【由乃救爷爷】
noip
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?
![](https://cdn.luogu.com.cn/upload/pic/5789.png)
肯定不是
那个算法有一个问题
就是查询的两个点都在同一个块中会出偏差
但是
块大小logn啊
所以复杂度最坏是nlogn
然而我可以微调块大小让你根本没法卡
然后这个题数据随机是不是
设块大小为x
则两个端点同一个块概率为1/x,代价为O( x )
所以可以让x = sqrt( n )因为预处理ST表挺慢的
这样就可以解决了
期望下O( n )的rmq
而且不用笛卡尔树什么的,常数超级小哦~
这个大概是一个不错的rmq算法,跑得又快,常数又小,还好写
重点是没人卡你,卡还不一定卡的住,还要冒着被暴力AC的风险
最后放上183炸鱼图
![](https://cdn.luogu.com.cn/upload/pic/5788.png)