• 周六. 10月 8th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

二次离线莫队

admin

11月 28, 2021

莫队的二次离线说难也难,说简单也简单,主要是看你对莫队的理解是否深刻。
这个算法说白了,就是把复杂度拆开,比如一个你莫队的时候一次移动复杂度是 (O(log n)),那么整体的复杂度就是 (O(nsqrt nlog n)),导致无法通过。
但是莫队虽然是一个离线算法,但是它的左右端点移动造成的贡献差的计算却是在线的,我们可以把这个在线的东西再次离线下来计算,对复杂度进行进一步的优化。

先来一个例题
对于这题,我们如果莫队之后暴力计算贡献(使用树状数组)的复杂度是 (O(nsqrt nlog n)) 的。
但是我们可以发现,每次移动右端点时,左端点总是不变的,所以我们可以通俗的写成 (f(x,l,r)) 是左端点是 (x),右端点从 (l-1) 变到 (r) 所造成的贡献,然后我们可以根据之前的式子推一下。
(g(x,y)) 表示右端点从 (y-1) 变成 (y) 造成的贡献,那么 (f(x,l,r)=sum_{i=l}^r g(x,i)),然后我们对于 (x) 排个序之后值域分块,就可以做到 (O(sqrt n)) 计算贡献。
而固定右端点移动左端点的时候同理。

发表回复

您的电子邮箱地址不会被公开。