历史研究问题
解题思路
本题给定一个序列,有若干个查询,每次询问一段区间中所有事件的重要度的最大值。
本题如果要用莫队算法来做,就需要考虑如何通过上一个查询的信息得出当前查询的信息,这里需要维护一个 $cnt$ 数组表示每个数出现的次数,假设上一个查询的区间是 $[i, j]$,当前查询的区间是 $[l, r]$,在从 $[i, j]$ 向 $[l, r]$ 转变的过程中,我们需要将一些数加入,也需要将一些数移除,对于加入一个数 $x$,由于题目保证 $x > 0$,因此在加入一个 $x$ 后,$x$ 的重要度是一定会严格变大的,因此对于结果只需要再用 $x$ 的新重要度更新一下即可。所以加入一个数是可以 $O(1)$ 直接维护的。
对于移除一个数,相当于将一个数的重要值减低,此时我们并不能确定重要度最大值是多少,有可能还是这个数,也有可能是别的数。而对于这种加入简单,删除难的情况,就可以使用回滚莫队来进行优化。
首先将所有查询先按照 $l$ 所在块的编号从小到大排序,再按照 $r$ 从小到大排序。然后我们一个块一个块的去考虑怎么做。对于某个块,我们先处理块内的所有询问,对于右端点在同一个块内的所有询问,由于块的长度不超过 $\sqrt{n}$,所以可以直接暴力求最大值。剩下的所有询问的右端点一定是在后面某个块中,此时我们将当前维护信息的区间的左端点 $i$ 固定到下一个块的第一个位置,将右端点 $j$ 固定到 $j$ 的前面一位,表示最开始维护的区间是空的,然后我们将询问区间分成两部分来做,第一部分是在当前块内的,第二部分是不在当前块内的。对于第二部分,由于这一部分的数都在 $j$ 的后面,因此这些数都会通过插入的方式加入到维护的区间中,而插入操作是 $O(1)$ 的,所以不需要任何其他操作,直接一一插入即可。此时不管是 $cnt$ 还是 $res$ 表示的都是第二部分的信息,也就是不包含当前块内的部分的信息。而对于第一部分,也就是块内的部分,由于块的长度很有限,因此我们每次可以直接暴力的将第一部分的数加入维护的区间中,计算完后再暴力的删掉即可。而这里的删除,由于删除操作不容易维护的只有 $res$,而 $cnt$ 数组是很容易删的,因此这里暴力删除只删除 $cnt$ 中的数,我们只需要在一开始就存下来 $res$ 的初始值,等把这一部分删完,再把存下来的备份还原回来即可,并不需要费力的去维护 $res$。
到此,我们的操作分为两种,一种是块内的询问,直接暴力做,时间是 $O(\sqrt{n})$ 的,一种是块间的询问,分成两个部分,右边部分和普通莫队一样,左边部分也是暴力求,时间也是 $O(\sqrt{n})$。因此总共的操作时间是不会超时 $O(n\sqrt{n})$ 的。这就是回滚莫队,核心思想就是对于不方便删除的部分,在较短的时间内进行暴力回滚,在时间复杂度较低的条件下,还能方便的处理删除操作。
注意,序列中每个数的范围在 $1 \sim 10^9$,$cnt$ 数组没法开这个大的空间,因此需要先进行离散化。
C++ 代码
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 100010;
struct Query
{
int id, l, r; //编号、左端点、右端点
}q[N]; //存储所有查询
int n, m, len; //序列长度、询问次数、每个块的长度
//原序列、每个下标所在的块编号、当前维护区间中每个数出现的次数
int w[N], id[N], cnt[N];
LL res[N]; //记录每个询问的答案
vector<int> nums; //离散化
int find(int x) //返回 x 离散化后的值
{
int l = 0, r = nums.size() - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(nums[mid] <= x) l = mid;
else r = mid - 1;
}
return r;
}
//先按照 l 所在块的编号从小到大排序,再按照 r 从小到大排序
bool cmp(const Query &a, const Query &b)
{
if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
return a.r < b.r;
}
void add(int x, LL &res) //在维护区间中加入 x,并更新 res
{
cnt[x]++;
res = max(res, (LL)cnt[x] * nums[x]);
}
int main()
{
scanf("%d%d", &n, &m);
len = sqrt(n); //计算块的长度
for(int i = 1; i <= n; i++) id[i] = (i - 1) / len; //预处理每个下标所在的块编号
for(int i = 1; i <= n; i++)
{
scanf("%d", &w[i]);
nums.push_back(w[i]);
}
//离散化
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
for(int i = 1; i <= n; i++) w[i] = find(w[i]); //将每个数替换为离散化后的数
for(int i = 0; i < m; i++)
{
int l, r;
scanf("%d%d", &l, &r);
q[i] = {i, l, r};
}
//将所有询问先按照 l 所在块的编号从小到大排序,再按照 r 从小到大排序
sort(q, q + m, cmp);
//回滚莫队
for(int x = 0; x < m; )
{
int y = x;
while(y < m && id[q[y].l] == id[q[x].l]) y++; //找出所有左端点在同一个块内的查询
int right = id[q[x].l] * len + len; //计算当前块的最后一个位置
//暴力求块内的询问
while(x < y && q[x].r <= right) //对于所有左、右端点在同一块内的询问直接暴力计算
{
LL ans = 0; //记录答案
int num = q[x].id, l = q[x].l, r = q[x].r;
for(int k = l; k <= r; k++) add(w[k], ans); //加入查询区间内的所有数
res[num] = ans; //更新答案
for(int k = l; k <= r; k++) cnt[w[k]]--; //将加入的所有数删去(还原)
x++; //计算下一个询问
}
//求块外的询问
LL ans = 0; //记录答案
int i = right + 1, j = right; //维护区间的左、右端点
while(x < y) //剩下所有的询问都是右端点在当前块以外的,都用暴力回滚的方式计算
{
int num = q[x].id, l = q[x].l, r = q[x].r;
while(j < r) add(w[++j], ans); //将查询区间右边块外部分的数加入
LL bans = ans; //备份当前状态下的答案
while(i > l) add(w[--i], ans); //将查询区间左边块内部分的数加入
res[num] = ans; //记录答案
while(i < right + 1) cnt[w[i++]]--; //将左边块内部分的数删去
ans = bans; //还原答案
x++; //计算下一个询问
}
memset(cnt, 0, sizeof cnt); //对于每个块,最开始维护区间都是空的,因此将重置 cnt 数组
}
for(int i = 0; i < m; i++) printf("%lld\n", res[i]);
return 0;
}