回滚莫队

发表于 更新于 Changyan：

例题：历史的研究

题目描述

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

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

事件有种类之分。第 $i$ 天发生的事件的种类用一个整数 $X_i$
表示，$X_i$ 越大，事件的规模就越大。

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

  • 选择日记中连续的几天 $[L,R]$ 作为分析的时间段；

  • 定义事件 $A$ 的重要度 $W_A$ 为 $A\times T_A$，其中 $T_A$ 为该事件在区间 $[L,R]$ 中出现的次数。

现在，您需要帮助教授求出所有事件中重要度最大的事件是哪个，并输出其重要度。

注意：教授有多组询问。

输入格式

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

接下来一行 $N$ 个空格分隔的整数表示每天的事件种类。

接下来 $Q$ 行，每行给出 $L,R$ 表示一组询问。

输出格式

输出共有 $Q$ 行，每行一个整数，表示对应的询问的答案。

数据范围

对于 $100%$ 的数据，$1\le Q,N\le 10^5$，$1\le X\le 10^9$，$1\le L\le R\le 10^5$。

样例输入 #1

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

样例输出 #1

1
2
3
4
5
9
8
8
16
16

样例输入 #2

1
2
3
4
5
6
8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8

样例输出 #2

1
2
3
4
27
18
19
19

样例输入 #3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
12 15
15 9 3 15 9 3 3 8 16 9 3 17
2 7
2 5
2 2
1 12
4 12
3 6
11 12
1 7
2 6
3 5
3 10
7 10
1 4
4 8
4 8

样例输出 #3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
18
18
9
30
18
15
17
30
18
15
18
16
30
15
15

一、回滚莫队算法

分析题目，没有修改，只有问询，似乎只是一个普通莫队。但如果用普通莫队去做就会发现写不了删点操作，因为无法确定删除掉的是不是最大的那个。

所以我们就改变一下思路：
既然删点难写那么咱们就改变思路：不删点。
但每个问询区间大小不一，无法保持只加点不删点。
其实可以保持右端点只增不减，对于左端每次增点后用暴力把增点数据删除（即回滚）即可。

8330_15bc7d0015-BZOJ4241-01.jpg

由于要保证右端点只增不减，即不能使用奇偶优化。排序函数这么写

1
2
3
4
5
6
sort(q, q + m, [&](const Query &x, const Query &y) {
        int i = get(x.l), j = get(y.l);
        // 回滚莫队不能用奇偶优化
        if(i == j) return x.r < y.r;
        return i < j;
    });

二、完整代码

时间复杂度：$O(M\sqrt{N})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 100010;

int len;
struct Query {
    int id, l, r;
} q[N];

int n, m;
int a[N];
int cnt[N];
LL res[N];

vector<int> nums;

int get(int x)
{
    return x / len;
}

void add(int x, LL &sum)
{
    cnt[x] ++;
    sum = max(sum, (LL)cnt[x] * nums[x]);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]), nums.push_back(a[i]);
    len = sqrt(n);
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    for(int i = 1; i <= n; i ++) 
        a[i] = lower_bound(nums.begin(), nums.end(), a[i]) - nums.begin();
    
    for(int i = 0; i < m; i ++) 
    {
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = {i, l, r};
    }
    
    sort(q, q + m, [&](const Query &x, const Query &y) {
        int i = get(x.l), j = get(y.l);
        // 回滚莫队不能用奇偶优化
        if(i == j) return x.r < y.r;
        return i < j;
    });
    
    for(int x = 0; x < m; )
    {
        int y = x;
        while(y < m && get(q[x].l) == get(q[y].l)) y ++;
        // 当前块最靠右的端点: k * len + len - 1
        int mr = get(q[x].l) * len + (len - 1);
        
        // 暴力求解块内
        while(x < y && get(q[x].l) == get(q[x].r))
        {
            LL sum = 0;
            int id = q[x].id, l = q[x].l, r = q[x].r;
            for(int i = l; i <= r; i ++) add(a[i], sum);
            res[id] = sum;
            for(int i = l; i <= r; i ++) cnt[a[i]] --;
            x ++;
        }
        
        // 求解块间
        LL sum = 0;
        int i = mr, j = mr + 1;
        while(x < y)
        {
            int id = q[x].id, l = q[x].l, r = q[x].r;
            while(i < r) add(a[++ i], sum);
            // 每次备份块外的sum, 后续回滚
            LL backup = sum;
            while(j > l) add(a[-- j], sum);
            res[id] = sum;
            // 回滚
            while(j < mr + 1) cnt[a[j ++]] --;
            sum = backup;
            x ++;
        }
        // 每次记得清空cnt, 保证每块的操作前, cnt数组是空的
        // 只会执行sqrt(n)次, 不会影响时间复杂度
        memset(cnt, 0, sizeof cnt);
    }
    for(int i = 0; i < m; i ++) printf("%lld\n", res[i]);
    return 0;
}