早就学过了,学了就只学了
不能再颓下去了
莫队
一般用来解决静态区间询问问题,如果 \([l,r]\) 的答案能扩展到 \([l\pm\mathtt{1},r\pm\mathtt{1}]\),那么我们就能使用莫队在 \(O(n\sqrt{n})\) 复杂度内完成所有询问的答案,这里设 \(n,m\) 同阶。这个根号怪死了,还有我删除线咋还没了/fn
思想很简单,将询问离线后排序,暴力从上一个区间的答案转移到下一个区间答案(一步一步移动即可)。
排序一般按 \(l\) 所在块的编号为第一关键字,\(r\) 为第二关键字,一般也会加玄学的奇偶性排序。还有一般的块长都设 \(\dfrac{n}{\sqrt{m}}\),不同的莫队理论最优的块长也不同。
一般核心在于这里:
ll l=1,r=0,res=0; //res是答案
for(int i=1;i<=m;++i){
阿巴阿巴;
while(l>q[i].l) add(--l);
while(l<q[i].l) del(l++);
while(r>q[i].r) del(r--);
while(r<q[i].r) add(++r);
ans[q[i].id]=res;
}
做几道题就懂了。
回滚莫队
因为要做题就先写这个了。
OI-wiki上的描述:有些题目在区间转移时,可能会出现增加或者删除无法实现的问题。在只有增加不可实现或者只有删除不可实现的时候,就可以使用回滚莫队在 \(n\sqrt{m}\) 的时间内解决问题。回滚莫队的核心思想就是:既然只能实现一个操作,那么就只使用一个操作,剩下的交给回滚解决。回滚莫队分为只增和只减,具体看题目。
例题:歴史の研究
我们发现增加一个元素很好解决,它若要对答案产生影响就一定是新的最大值,但删除元素时我们不好判断剩下区间中的最大重要值是啥,这个时候就是只增加莫队了。
操作过程如下(不想写直接粘了):
-
对原序列进行分块,对询问按以左端点所属块编号升序为第一关键字,右端点升序为第二关键字的方式排序。
-
按顺序处理询问:
-
如果询问左端点所属块 \(B\) 和上一个询问左端点所属块的不同,那么将莫队区间的左端点初始化为 \(B\) 的右端点加 \(1\), 将莫队区间的右端点初始化为 \(B\) 的右端点;
-
如果询问的左右端点所属的块相同,那么直接扫描区间回答询问;
-
如果询问的左右端点所属的块不同:
-
如果询问的右端点大于莫队区间的右端点,那么不断扩展右端点直至莫队区间的右端点等于询问的右端点;
-
不断扩展莫队区间的左端点直至莫队区间的左端点等于询问的左端点;
-
回答询问;
-
撤销莫队区间左端点的改动,使莫队区间的左端点回滚到 \(B\) 的右端点加 \(\mathtt{1}\)。
-
-
复杂度不想证,块长最优取 \(\dfrac{n}{\sqrt{m}}\),当然有时候更玄学的更好,但稳妥起见还是用这个,正式赛应该不怎么卡常吧。
还是把代码写了才能理解,多做几道题就上手了。
标签:回滚,询问,sqrt,端点,区间,数据结构,莫队 From: https://www.cnblogs.com/heshuwan/p/17991881