抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

传送门 考虑把所有线段按照长度排序,在排好序的序列上面跑尺取法,设尺取法维护的区间为[pl,pr][pl,pr][pl,pr],一直移动右端点prprpr,直到现在有一个点在区间[pl,pr][pl,pr][pl,pr]代表的线段上面出现>=m>=m>=m次,停止移动右端点,开始移动左端点,直到没有点在区间[pl,pr][pl,pr][pl,pr]代表的线段上面出现>...

传送门 考虑尺取法求出所有满足条件的i,ji,ji,j,使∑k=ijFk>=M\sum ^j _{k=i}F_k>=M∑k=ij​Fk​>=M,O(n)O(n)O(n)即可求出。 再考虑如何求max⁡(Si,Si+1,...Sj−1,Sj)\max(S_i,S_{i+1},...S_{j-1},S_j)max(Si​,Si+1​,...Sj−1​,Sj​) 用线段树预处理即...