回滚莫队学习笔记

AzusidNya の部屋 / 2023-08-24 / 原文

板子题交 \(998244353\) 遍一直 UKE 我哭死。

回滚莫队

有些题看起来像个莫队，想着想着发现 add 操作很容易实现，而 del 操作怎么都想不出来，或者是 del 操作时间复杂度不是 \(O(1)\) 时间复杂度爆炸，那么回滚莫队就能派上用场。这种莫队不带删因此也叫做不带删莫队。

AT_joisc2014_c 歴史の研究

给你一个长度为 \(n\) 的数组 \(A\) 和 \(m\) 个询问 \((1 \leq n, m \leq 10^5)\)，每次询问一个区间 \([L, R]\) 内重要度最大的数字，要求输出其重要度。一个数字 \(i\) 重要度的定义为 \(i\) 乘上 \(i\) 在区间内出现的次数。

sol:

从莫队的角度出发，首先我们尝试实现 add 和 del 函数。

add 函数：在当前区间内增加一个数并更新答案。加入数 \(x\) 后令 \(cnt_x \leftarrow cnt_x + 1\) 然后更新答案即可。

del 函数：？好像很难 \(O(1)\) 实现。因为删除最大值后好像没法快速找回次小值。

那怎么办？不要删除操作就行了。

首先还是很正常的莫队分块+排序。

然后按顺序处理询问：

如果询问的左端点跳到了新的一块，那么将左右指针扔到当前块的右边形成空集。
如果询问的左右端点在同一块内，直接暴力即可。
往右跳右指针到右端点。
然后往左跳左指针到左端点。
到位后回答询问。
撤销之前的修改，把指针挪回去。

注意这里的撤销并不是删除，撤销的方法很多，例如这题就是直接记录原位的答案，然后再把 \(cnt\) 一路滚回去。

这样我们就做到了不带删除完成莫队的内容。

时间复杂度方面，不是很会证明。设询问数量是 \(q\) 且与 \(n\) 同阶，我的感性理解就是左端点一直只在一块内扫，变化量在块长 \(T\) 以内，变化次数与块的个数和询问个数有关当块长取根号级别的而右端点往右扫所以是个 \(O(n)\) 。块长取 \(\large\frac{n}{\sqrt{q}}\) 是最优的，时间复杂度 \(n \sqrt{q}\)，当然如果 \(n\) 和 \(q\) 不同阶那还需要再仔细调整下块长。

code:

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n, Q, N, T, bl, tmp;
int a[100005], b[100005];
int L[100005], R[100005];
int belong[100005];
int ans[100005];
struct Query{
	int l, r, id;
}q[100005];
bool cmp(Query u, Query v){
	return belong[u.l] == belong[v.l] ? u.r < v.r : u.l < v.l;
}
int cn[100005], cnt[100005];
int solve(int l, int r){
	int ans = 0;
	for(int i = l; i <= r; i ++)
		cn[a[i]] ++;
	for(int i = l; i <= r; i ++)
		ans = max(ans, cn[a[i]] * b[a[i]]);
	for(int i = l; i <= r; i ++)
		cn[a[i]] --;
	return ans;
}
int add(int x){
	cnt[a[x]] ++;
	tmp = max(tmp, cnt[a[x]] * b[a[x]]);
	return 0;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0); 
	cin >> n >> Q;
	for(int i = 1; i <= n; i ++)
		cin >> a[i], b[i] = a[i];
	for(int i = 1; i <= Q; i ++)
		cin >> q[i].l >> q[i].r, q[i].id = i;
	sort(b + 1, b + n + 1);
	N = unique(b + 1, b + n + 1) - b - 1;
	for(int i = 1; i <= n; i ++)
		a[i] = lower_bound(b + 1, b + N + 1, a[i]) - b;
	T = sqrt(n), bl = n / T;
	for(int i = 1; i <= n; i ++)
		L[i] = R[i - 1] + 1, R[i] = L[i] + T - 1;
	if(R[bl] < n) ++ bl, L[bl] = R[bl - 1] + 1, R[bl] = n;
	for(int i = 1; i <= n; i ++)
		belong[i] = (i - 1) / T + 1;
	sort(q + 1, q + Q + 1, cmp);
	for(int i = 1, r = 0, l = 0, nw = 1; i <= bl; i ++){
		memset(cnt, 0, sizeof(cnt));
		r = R[i];
		tmp = 0;
		while(belong[q[nw].l] == i){
			l = R[i] + 1;
			if(q[nw].r - q[nw].l <= T){
				ans[q[nw].id] = solve(q[nw].l, q[nw].r);
				++ nw;
				continue;
			}
			while(q[nw].r > r) add(++ r);
			int ret = tmp;
			while(l > q[nw].l)
				add(-- l);
			ans[q[nw].id] = tmp;
			tmp = ret;
			while(l <= R[i])
				cnt[a[l ++]] --;
			++ nw;
		}
	}
	for(int i = 1; i <= Q; i ++)
		cout << ans[i] << "\n";
	return 0;
}

另外一直在 UKE 我也不知道对不对反正样例是过了。