almost 3 years ago

今天考试出题人Dash出了一道莫队题,恰好之前对莫队算法有没有完全理解,今天又重新看了一下。

对于询问,如果我们可以在的时间内推出询问的话,我们就可以将回答所有询问的时间降到

那么如何实现呢?
我们先把询问按左端点排序,再将其顺序分成块。
然后在每个块内按照右端点排序,依次回答询问即可。

这里的回答询问是这样的:
$$[l,r]\Rightarrow[l,r+p],insert(a[r+1]...a[r+p])$$$$[l,r]\Rightarrow[l-p,r],insert(a[l-p]...a[l-1])$$$$[l,r]\Rightarrow[l+p,r],delete(a[l+1]...a[l+p-1])$$$$[l,r]\Rightarrow[l,r-p],delete(a[r-p+1]...a[r])$$
也就是说我们每一询问都是由上一个询问推出来的。

现在我们来证明时间复杂度:

1.对于右端点:
如果询问在同一个块中,那么这个块内的询问中右端点最多转移次,又因为块的个数为,因此为
如果询问在相邻的两个块中,那么一次最多转移次,又因为块数为,所以时间复杂度为

2.对于左端点:
如果两个询问在同一个块中,那么最多转移次,又因为有个询问,所以时间复杂度为
如果两个询问在相邻两个块中,那么这种转移左端点只会一直右移,是线性的

综上所述,时间复杂度就是

over,啦啦啦

← New Beginning splay模板(poj3580) →
 
comments powered by Disqus