回滚莫队学习笔记 (笔记+模板)
回滚莫队
今天学习了回滚莫队，忍不住手痒写一下学习笔记。（bushi
回滚莫队其实十分的简单易懂。
为什么需要回滚莫队呢？
普通的莫队可以O(1)维护从(L , R)转移到(L ± 1 , R) , (L , R ± 1)，但是，有一些维护值 扩展容易收缩难，或者 收缩容易扩展难。
比如，最大值的维护就是扩展容易收缩难。举个例子：365bet体育在线们要从(L , R)转移到(L+1 , R)，那么aL就不在区间中了，可是365bet体育在线们很难判断aL是否为(L , R)中的最大值，如果是，且唯一，则(L+1 , R)的最大值就不再是aL，因为aL已经被移出区间，365bet体育在线们也不知道(L+1 , R)的最大值究竟是多少。这样，就无法转移了。
此时，回滚莫队闪亮登场！
回滚莫队的思想
只在左端点在同一分块内时才转移。当左端点在新的分块内时，初始化所有。
因为左端点在同一分块内的是按右端点排序，365bet体育在线右端点肯定是单向扩展或收缩的，像普通莫队一样扩展即可。
左端点是乱序的，365bet体育在线每次都从当前分块的右边界开始往左边扩展到左端点，这样就只会扩展而不会面临收缩的局面（如果是收缩容易扩展难就从左边界开始收缩）。
时间复杂度依然是O(n√n)。
回滚莫队的具体实现（扩展容易收缩难为例）
1. 对原序列进行分块，并对询问按照如下的方式排序：以左端点所在的块升序为第一关键字，以右端点升序为第二关键字。（注意：365bet体育在线们不能使用奇偶优化）
2. 遍历所有分块。
3. 365bet体育在线们先将莫队当前分块区间左端点初始化为分块的右边界+1，右端点初始化为分块块的右边界，这是一个空区间。
4. 左右端点在同一个分块中的询问，365bet体育在线们直接暴力遍历即可。然后再遍历一次修改回原样。
5. 左右端点不在同一个分块中的询问，一直扩展莫队区间右端点直到区间右端点与询问右端点重合。区间左端点每次都从当前分块的右边界开始往左边扩展到左端点。然后再把区间左端点扫回分块右边界+1，把所有数据修改回原样。（回滚）
6. 所有左端点在当前分块内的询问遍历结束后，清空所有数据。（就是把区间右端点扫回分块右边界）（回滚）
下面，365bet体育在线们来看一道板子题：
洛咕 AT1219 历史研究
题目描述
IOI国历史研究的第一人——JOI教授，最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活，开始着手调查日记中记载的事件。
日记中记录了连续N天发生的时间，大约每天发生一件。
事件有种类之分。第i天(1≤i≤N)发生的事件的种类用一个整数Xi365体育投注，Xi越大，事件的规模就越大。
JOI教授决定用如下的方法分析这些日记：
1.选择日记中连续的一些天作为分析的时间段
2.事件种类t的重要度为t*(这段时间内重要度为t的事件数)
3.计算出所有事件种类的重要度，输出其中的最大值
现在你被要求制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。
输入格式
第一行两个空格分隔的整数N和Q，365体育投注日记一共记录了N天，询问有Q次。 接下来一行N个空格分隔的整数X1...XN，Xi365体育投注第i天发生的事件的种类 接下来Q行，第i行(1≤i≤Q)有两个空格分隔整数Ai和Bi，365体育投注第i次询问的区间为[Ai,Bi]。
输出格式
输出Q行，第i行(1≤i≤Q)一个整数，365体育投注第i次询问的最大重要度
样例
输入样例
5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4
输出样例
9
8
8
16
16
数据范围与提示
1≤N≤105, 1≤Q≤105, 1≤Xi≤109 (1≤i≤N)
这题就是模版题，只是要注意两点，一是离散化，二是开long long
不多说了，上代码 （可以当模板用，自认为码风还是比较易懂的）
1 //回滚莫队 2 //洛咕AT1219 历史研究 3 4 #include <iostream> 5 #include <algorithm> 6 #include <cstdio> 7 #include <cstring> 8 #include <cmath> 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<'0' || 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; i<=n; i++){ 50 a[i]=read(); 51 b[i]=a[i]; //离散化 52 if(i>sum){ 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; j<=m; j++){ 66 int l=no[j].l,r=no[j].r; 67 if(l>min(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(you<r){ //扩展右端点 82 you++; 83 num[v[you]]++; 84 now=max(now,1ll*b[you]*num[v[you]]); 85 }tmp=now; //tmp记录此时的now值 86 while(zuo>l){ //扩展左端点 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(zuo<k+sq){ //回滚左端点 93 num[v[zuo]]--; 94 zuo++; 95 } 96 }while(you>k+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 }