回滚莫队学习笔记
回滚莫队
今天学习了回滚莫队，忍不住手痒写一下学习笔记。（bushi
回滚莫队其实十分的简单易懂。
为什么需要回滚莫队呢？
普通的莫队可以O(1)维护从(L , R)转移到(L ± 1 , R) , (L , R ± 1)，但是，有一些维护值 扩展容易收缩难，或者 收缩容易扩展难。
比如，最大值的维护就是扩展容易收缩难。举个例子：我们要从(L , R)转移到(L+1 , R)，那么a L
就不在区间中了，可是我们很难判断a L
是否为(L , R)中的最大值，如果是，且唯一，则(L+1 , R)的最大值就不再是a L
，因为a L
已经被移出区间，我们也不知道(L+1 , R)的最大值究竟是多少。这样，就无法转移了。
此时，
回滚莫队
闪亮登场！
回滚莫队的思想
只在左端点在同一分块内时才转移。当左端点在新的分块内时，初始化所有。
因为左端点在同一分块内的是按右端点排序，所以右端点肯定是单向扩展或收缩的，像普通莫队一样扩展即可。
左端点是乱序的，所以每次都从当前分块的右边界开始往左边扩展到左端点，这样就只会扩展而不会面临收缩的局面（如果是收缩容易扩展难就从左边界开始收缩）。
时间复杂度依然是O(n√n)。
回滚莫队的具体实现（扩展容易收缩难为例）
1. 对原序列进行分块，并对询问按照如下的方式排序：以左端点所在的块升序为第一关键字，以右端点升序为第二关键字。（ 注意：我们不能使用奇偶优化
）
2. 遍历所有分块。
3. 我们先将莫队当前分块区间左端点初始化为分块的右边界+1，右端点初始化为分块块的右边界，这是一个空区间。
4.
左右端点在同一个分块中的询问
，我们直接暴力遍历即可。然后再遍历一次修改回原样。
5.
左右端点不在同一个分块中的询问
，一直扩展莫队区间右端点直到区间右端点与询问右端点重合。区间左端点每次都从当前分块的右边界开始往左边扩展到左端点。然后再把区间左端点扫回分块右边界+1，把所有数据修改回原样。（回滚）
6.所有左端点在当前分块内的询问遍历结束后，清空所有数据。（就是把区间右端点扫回分块右边界）（回滚）
下面，我们来看一道板子题：
洛咕 AT1219 历史研究
题目描述
IOI国历史研究的第一人——JOI教授，最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活，开始着手调查日记中记载的事件。
日记中记录了连续N天发生的时间，大约每天发生一件。
1
≤
i
≤
N)发生的事件的种类用一个整数X i
表示，X i
越大，事件的规模就越大。
JOI教授决定用如下的方法分析这些日记：
1.选择日记中连续的一些天作为分析的时间段
2.事件种类t的重要度为t*(这段时间内重要度为t的事件数)
3.计算出所有事件种类的重要度，输出其中的最大值
现在你被要求制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。
输入格式
第一行两个空格分隔的整数N和Q，表示日记一共记录了N天，询问有Q次。 接下来一行N个空格分隔的整数
X 1
…X N
输出格式
输出Q行，第i行(
1
≤
i
≤
Q)一个整数，表示第i次询问的最大重要度
样例
输入样例
输出样例
数据范围与提示
1
≤
N
≤
1
0 5
,
1 //回滚莫队
2 //洛咕AT1219 历史研究
3
4 #include
5 #include
6 #include
7 #include
8 #include
9 #define ll long long
10 #define inf0x3f3f3f3f
11 using namespace std;
12 int read(){
13 int ret=0,ttt=1;
14 char ch=getchar();
15 while(ch'9'){
16 if(ch=='-'){
17 ttt=-1;
18 }ch=getchar();
19 }while(ch>='0' && ch<='9'){
20 ret=(ret<<1)+(ret<<3)+(ch^48);
21 ch=getchar();
22 }return ret*ttt;
23 }
24 struct dat{
25 int l,r,p; //询问左端点、右端点、询问编号（方便在排序后按输入顺序输出答案）
26 };
27 int n,m,sq;
28 int a[100005],pos[100005],num[100005],v[100005],b[100005]; //a 种类, b 存原来的a, v 离散值, pos[i] i属于的分块号, num 种类出现次数
29 ll ans[100005];
30 dat no[100005]; //询问
31 bool cmp(dat u, dat v){
32 if(pos[u.l]==pos[v.l]){
33 return u.r<v.r;
34 }return u.l<v.l;
35 }
36 int tt;
37 void in(){ //离散化（莫队不需要，是由于题目原因）
38 sort(a+1,a+n+1);
39 tt=n;
40 tt=unique(a+1,a+tt+1)-(a+1);
41 for(int i=1; i<=n; i++){
42 v[i]=lower_bound(a+1,a+tt+1,b[i])-a;
43 }
44 }
45 int main(){
46 n=read(),m=read();
47 sq=int(sqrt(n));
48 int sum=0,cnt=0;
49 for(int i=1; isum){
53 sum+=sq;
54 cnt++;
55 }pos[i]=cnt;
56 }in();
57 for(int i=1; i<=m; i++){
58 no[i].l=read(),no[i].r=read();
59 no[i].p=i;
60 }sort(no+1,no+m+1,cmp);
61 int p=1;
62 for(int k=1; k<=n; k+=sq){ //遍历所有块
63 int you=min(k+sq-1,n),zuo=you+1; //莫队区间左右端点
64 ll now=0,tmp=0;
65 for(int j=p; jmin(k+sq-1,n)){
68 p=j;
69 break;
70 }if(j==m){
71 p=m+1;
72 }if(pos[l]==pos[r]){ //特判：询问左右端点在同一块中
73 for(int i=l; i<=r; i++){ //暴力扫
74 num[v[i]]++;
75 now=max(now,1ll*b[i]*num[v[i]]);
76 }ans[no[j].p]=max(ans[no[j].p],now);
77 now=tmp;
78 for(int i=l; i<=r; i++){
79 num[v[i]]--; //回滚
80 }continue;
81 }while(youl){ //扩展左端点
87 zuo--;
88 num[v[zuo]]++;
89 now=max(now,1ll*b[zuo]*num[v[zuo]]);
90 }ans[no[j].p]=max(ans[no[j].p],now);
91 now=tmp; //回滚now值
92 while(zuok+sq-1){ //整个块遍历结束，回滚右端点
97 num[v[you]]--;
98 you--;
99 }
100 }for(int i=1; i<=m; i++){
101 printf("%lld\n",ans[i]);
102 }
103 return 0;
104 }
About The Author
maynard
懒散，不想无聊