前言
cf群里，有人提了一个经典问题，
0，形如这样的01序列，每次询问[l,r]间出现最多的连续1的个数，
区间连续1，不带修改的问题，都不带修改了，所以可以考虑更优的方法，
Claris口胡一个O(n)-O(1)的做法，于是来学习一下
思路来源
https://www.cnblogs.com/whx1003/p/13996517.html
知识总结
四毛子算法是一种暴力分块的思想，+-1RMQ是其应用之一
①+-1RMQ问题（O(n)-O(1)）
+-1RMQ问题是这么一个问题，仍然询问区间的RMQ，
但是这个序列有着特殊的性质，即相邻项之差要么是-1，要么是+1，
于是，有如下的暴力思想，先分块，每一块大小为B，则分为n/B块，
对于每一块的+-1情况，二进制枚举讨论，这里以最大值为例，
这样就能判断出来最大值的位置，多个位置选择其中一个即可，
对于这n/B块，每块存了一个最大值，运用朴素ST表的思想，
这样的复杂度就是
，
为了复杂度最优，我们取，则原复杂度为O(n)级别
其实这个B值，似乎取的时候更小，
可能考虑到实现的时候还带常数吧，实践意义上除以个2更优
这样就做到了O(n)的预处理，O(1)的查询
②O(n)-O(1)查询树上两点的lca
先求出原树的欧拉序，
注意到欧拉序只有相邻深度的变化，
即深度的变化只有+-1，这样就可以套用+-1RMQ的方法，
欧拉序求a和b的lca时，需要求第一次出现a的位置和第一次出现b的位置间深度最小值的点，
于是这便可以对原序列进行+-1RMQ查询
③O(n)-O(1)求一个任意序列的RMQ
先对原序列扫一遍，建笛卡尔树，
就转化为树上问题，再套用+-1RMQ的方法，
即可实现求任意序列的RMQ
后续
考虑原问题，0011100这样的序列，
先转化一步把0合并，转化为01110，
再转化一步，把连续1压到一起，变为030，
但是这不满足+-1的渐变过程，所以考虑补出一些项来，变为0，
这相比原序列来说，最多扩展为原长的二倍，因此是可行的，
对于询问的[l,r]来说，可能两端的段不是完整包含的，
这个预处理一下，
对于每个位置的1，与其位于同一个尺取段内的最后位置，
和与其位于同一个尺取段内的最初位置，即可实现两端点的特判
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/200971.html原文链接：https://javaforall.net
