『回滚莫队及其简单运用』

本是古典何须时尚 2021-11-27 03:08 283阅读 0赞

基础莫队和带修莫队可以看这个[课件][Link 1]。

--------------------

## 回滚莫队 ##

基础的莫队算法相信大家都已经熟悉了，而我们知道，莫队算法的关键就在于如何进行区间的转移，这就可能涉及到很多的细节。有一类普通莫队不可解的问题就是在转移区间过程中，可能出现删点或加点操作**其中之一**无法实现的问题。那么我们就来探讨如何利用特殊的莫队算法来解决这类问题，**而这种莫队算法就称之为回滚莫队算法**。

### 只加不减的回滚莫队 ###

我们考虑一个区间问题，若这个问题在区间转移中，加点操作得以实现，但是删点操作无法有效的实现时，就可以使用如下的莫队算法：

> \\(1.\\) 对原序列进行分块，并对询问按照如下的方式排序：**以左端点所在的块升序为第一关键字，以右端点升序为第二关键字**
> 
> \\(2.\\) 对于处理所有左端点在块\\(T\\)内的询问，我们先将莫队区间左端点初始化为\\(R\[T\]+1\\)，右端点初始化为\\(R\[T\]\\)，这是一个空区间
> 
> \\(3.\\) 对于左右端点在同一个块中的询问，我们直接暴力扫描回答即可。
> 
> \\(4.\\) 对于左右端点不在同一个块中的所有询问，由于其右端点升序，我们对右端点只做加点操作，总共最多加点\\(n\\)次
> 
> \\(5.\\) 对于左右端点不在同一个块中的所有询问，其左端点是可能乱序的，我们每一次从\\(R\[T\]+1\\)的位置出发，只做加点操作，到达询问位置即可，每一个询问最多加\\(\\sqrt n\\)次。回答完询问后，**我们撤销本次移动左端点的所有改动，使左端点回到\\(R\[T\]+1\\)的位置**
> 
> \\(6.\\) 按照相同的方式处理下一块

根据其操作的过程可知，回滚莫队的时间复杂度仍然为\\(O(n\\sqrt n)\\)，并且，在回答询问的过程中我们只进行了加点操作，没有涉及删点操作，这样就完成了我们需要的操作。

### 只减不加的回滚莫队 ###

和上一种典型的回滚莫队类似，我们还可以实现只有删点操作没有加点操作的回滚莫队，当然，这样的前提是我们可以正确的先将整个序列加入莫队中，那么算法流程如下：

> \\(1.\\) 对原序列进行分块，并对询问按照如下的方式排序：**以左端点所在的块升序为第一关键字，以右端点降序序为第二关键字**
> 
> \\(2.\\) 对于处理所有左端点在块\\(T\\)内的询问，我们先将莫队区间左端点初始化为\\(L\[T\]\\)，右端点初始化为\\(n\\)，这是一个大区间
> 
> \\(3.\\) 对于左右端点在同一个块中的询问，我们直接暴力扫描回答即可。
> 
> \\(4.\\) 对于左右端点不在同一个块中的所有询问，由于其右端点降序，从\\(n\\)的位置开始，我们对右端点只做删点操作，总共最多删点\\(n\\)次
> 
> \\(5.\\) 对于左右端点不在同一个块中的所有询问，其左端点是可能乱序的，我们每一次从\\(L\[T\]\\)的位置出发，只做删点操作，到达询问位置即可，每一个询问最多加\\(\\sqrt n\\)次。回答完询问后，**我们撤销本次移动左端点的所有改动，使左端点回到\\(L\[T\]\\)的位置**
> 
> \\(6.\\) 按照相同的方式处理下一块

同样地，回滚莫队的时间复杂度还是\\(O(n\\sqrt n)\\)，并且我们只使用了删点操作，只有在一开始时将整个序列加入到莫队中，这样就完成了我们需要的操作。

那么我们将通过两道例题来详细地了解整两种回滚莫队。

## 歴史の研究 ##

### Description ###

IOI国历史研究的第一人——JOI教授，最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活，开始着手调查日记中记载的事件。

日记中记录了连续N天发生的时间，大约每天发生一件。

事件有种类之分。第i天(1<=i<=N)发生的事件的种类用一个整数X\_i表示，X\_i越大，事件的规模就越大。

JOI教授决定用如下的方法分析这些日记：

1.  选择日记中连续的一些天作为分析的时间段
2.  事件种类t的重要度为t\*(这段时间内重要度为t的事件数)
3.  计算出所有事件种类的重要度，输出其中的最大值 现在你被要求制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。

### Input Format ###

第一行两个空格分隔的整数N和Q，表示日记一共记录了N天，询问有Q次。

接下来一行N个空格分隔的整数X\_1...X\_N,X\_i表示第i天发生的事件的种类

接下来Q行，第i行(1<=i<=Q)有两个空格分隔整数A\_i和B\_i，表示第i次询问的区间为\[A\_i,B\_i\]。

### Output Format ###

输出Q行，第i行(1<=i<=Q)一个整数，表示第i次询问的最大重要度

### Sample Input ###

5 5
    9 8 7 8 9
    1 2
    3 4
    4 4
    1 4
    2 4

### Sample Output ###

9
    8
    8
    16
    16

### 解析 ###

大致题意：给定一个长度为\\(n\\)的序列，离线询问\\(m\\)个问题，每次回答区间内元素权值乘以元素出现次数的最大值。

我们考虑用莫队来解决这个问题，显然，为了统计每个元素的出现次数，我们要用到桶。而加点操作就很好实现了，在桶中给元素的出现次数加一，并查看是否能够更新答案即可。但是删点操作就难以实现，当我们删去一个点时，我们难以得知新的最大值是多少，所以我们用只加不减的回滚莫队。

那么回滚莫队中提到的撤销操作具体就是指在桶中减去出现次数，而不管答案是否改变。在下一次加点的过程中，答案就得以统计了。

\\(Code:\\)

#include <bits/stdc++.h> using namespace std; const int N = 1e5+20 , SIZE = 1020; int n,m,size,T,raw[N],val[N],t,cnt[N],cnt_[N]; int belo[N],L[SIZE],R[SIZE]; long long ans[N],Max,a[N]; struct query{int l,r,id;}q[N]; inline void input(void) { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%lld",&a[i]) , raw[++t] = a[i]; for (int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r) , q[i].id = i; } inline void discrete(void) { sort( raw+1 , raw+t+1 ); t = unique( raw+1 , raw+t+1 ) - (raw+1); for (int i=1;i<=n;i++) val[i] = lower_bound( raw+1 , raw+t+1 , a[i] ) - raw; } inline void setblocks(void) { size = sqrt(n) , T = n/size; for (int i=1;i<=T;i++) { if ( i * size > n ) break; L[i] = (i-1) * size + 1; R[i] = i * size; } if ( R[T] < n ) T++ , L[T] = R[T-1] + 1 , R[T] = n; for (int i=1;i<=T;i++) for (int j=L[i];j<=R[i];j++) belo[j] = i; } inline bool compare(query p1,query p2) { if ( belo[p1.l] ^ belo[p2.l] ) return belo[p1.l] < belo[p2.l]; else return p1.r < p2.r; } // 加点 inline void insert(int p,long long &Maxval) { cnt[val[p]]++; Maxval = max( Maxval , 1LL * cnt[val[p]] * a[p] ); } // 撤销 inline void resume(int p) { cnt[val[p]]--; } inline void CaptainMo(void) { sort( q+1 , q+m+1 , compare ); int l = 1 , r = 0 , lastblock = 0; for (int i=1;i<=m;i++) { // 处理同一块中的询问 if ( belo[q[i].l] == belo[q[i].r] ) { for (int j=q[i].l;j<=q[i].r;j++) cnt_[val[j]]++; long long temp = 0; for (int j=q[i].l;j<=q[i].r;j++) temp = max( temp , 1LL * cnt_[val[j]] * a[j] ); for (int j=q[i].l;j<=q[i].r;j++) cnt_[val[j]]--; ans[ q[i].id ] = temp; continue; } // 如果移动到了一个新的块，就先把左右端点初始化 if ( lastblock ^ belo[q[i].l] ) { while ( r > R[belo[q[i].l]] ) resume(r--); while ( l < R[belo[q[i].l]]+1 ) resume(l++); Max = 0 , lastblock = belo[q[i].l]; } // 单调地移动右端点 while ( r < q[i].r ) insert(++r,Max); // 移动左端点回答询问 long long temp = Max; int l_ = l; while ( l_ > q[i].l ) insert(--l_,temp); // 回滚 while ( l_ < l ) resume(l_++); ans[ q[i].id ] = temp; } } int main(void) { input(); discrete(); setblocks(); CaptainMo(); for (int i=1;i<=m;i++) printf("%lld\n",ans[i]); return 0; }

## mex ##

### Description ###

有一个长度为n的数组\{a1,a2,…,an\}。m次询问，每次询问一个区间内最小没有出现过的自然数。

### Input Format ###

第一行n,m。

第二行为n个数。

从第三行开始，每行一个询问l,r。

### Output Format ###

一行一个数，表示每个询问的答案。

### Sample Input ###

5 5
    2 1 0 2 1
    3 3
    2 3
    2 4
    1 2
    3 5

### Sample Output ###

1
    2
    3
    0
    3

### 解析 ###

这道题我们莫队是思路就是用桶维护出现过的数字，那么\\(mex\\)值就是第一个不在桶中出现的数字。

我们发现删点操作很容易实现，可以顺带的更新答案，但是加点操作难以实现，我们原来的最小值在加点过程中出现了，我们就无从得知新的答案。显然，一开始将整个序列加入到桶里并统计答案是可行的，那么我们就是用只删不加的回滚莫队。

撤销操作还是在桶中更新，但不管答案的变化就可以了。

\\(Code:\\)

#include <bits/stdc++.h> using namespace std; const int N = 200020 , SIZE = 1020; int n,m,a[N],cnt[N],Min,size,T,ans[N]; int cnt_[N],ans_,belo[N],L[N],R[N]; struct query{int l,r,id;}q[N]; inline void input(void) { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r) , q[i].id = i; } inline void init(void) { for (int i=1;i<=n;i++) if ( a[i] <= n+1 ) cnt[ a[i] ]++; while ( cnt[ ans_ ] ) ans_++; // 先把整个序列加入桶，同时得到整体的答案 } inline void setblocks(void) { size = sqrt(n) , T = n/size; for (int i=1;i<=T;i++) { if ( i * size > n ) break; L[i] = (i-1)*size + 1; R[i] = i * size; } if ( R[T] < n ) T++ , L[T] = R[T-1] + 1 , R[T] = n; for (int i=1;i<=T;i++) for (int j=L[i];j<=R[i];j++) belo[j] = i; } inline bool compare(query p1,query p2) { if ( belo[p1.l] ^ belo[p2.l] ) return belo[p1.l] < belo[p2.l]; else return p1.r > p2.r; } // 删点 inline void remove(int p,int &Minval) { if ( a[p] > n+1 ) return; cnt[a[p]]--; if ( cnt[a[p]] == 0 ) Minval = min( Minval , a[p] ); } // 撤销 inline void resume(int p) { if ( a[p] > n+1 ) return; cnt[a[p]]++; } inline void CaptainMo(void) { sort( q+1 , q+m+1 , compare ); int l = 1 , r = n , lastblock = 0; for (int i=1;i<=m;i++) { // 处理同一块中的询问 if ( belo[q[i].l] == belo[q[i].r] ) { for (int j=q[i].l;j<=q[i].r;j++) if ( a[j] <= n+1 ) cnt_[a[j]]++; int temp = 0; while ( cnt_[temp] ) temp++; ans[ q[i].id ] = temp; for (int j=q[i].l;j<=q[i].r;j++) if ( a[j] <= n+1 ) cnt_[a[j]]--; continue; } // 如果移动到了一个新的块，就先把左右端点初始化 if ( belo[q[i].l] ^ lastblock ) { while ( r < n ) resume(++r); while ( l < L[belo[q[i].l]] ) remove(l++,ans_); Min = ans_ , lastblock = belo[q[i].l]; } // 单调地移动右端点 while ( r > q[i].r ) remove(r--,Min); // 移动左端点回答询问 int temp = Min , l_ = l; while ( l_ < q[i].l ) remove(l_++,temp); // 回滚 while ( l_ > l ) resume(--l_); ans[ q[i].id ] = temp; } } int main(void) { input(); init(); setblocks(); CaptainMo(); for (int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }

--------------------

转载于:https://www.cnblogs.com/Parsnip/p/10969989.html

[Link 1]: https://share.weiyun.com/51lWZEU