题解 P3793 【由乃救爷爷】

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炸鱼图