LOJ6285. 数列分块入门 9 - 离线区间众数 -- 回滚莫队

最近正在通过这个这个题集学习分块，做到最后一题求区间众数的时候百思不得其解，无奈去网上搜索题解。在搜索的过程中，许多博客都提到了一种叫做回滚莫队的算法，于是又去花了半天时间学习新技术，终于用回滚莫队来做出了这道题

题目链接 ： #6285. 数列分块入门 9 - 题目 - LibreOJ (loj.ac)

回滚莫队学习参考资料 ：『回滚莫队及其简单运用』

---

代码

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
const int maxn = 1e5;
struct Query {
	int l, r, id;
}q[maxn+10];
int a[maxn + 10];
int st[maxn + 10];
int ed[maxn + 10];
int bel[maxn + 10];

void init(int n) {
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	int sq;
	sq = sqrt(n);
	for (int i = 1; i <= n; i++) {
		st[i] = n / sq * (i - 1) + 1;
		ed[i] = n / sq * i;
	}
	ed[sq] = n;
	for (int i = 1; i <= sq; i++) {
		for (int j = st[i]; j <= ed[i]; j++) {
			bel[j] = i;
		}
	}
}
bool cmp(Query a, Query b) {
	if (bel[a.l] != bel[b.l])
		return bel[a.l] < bel[b.l];
	else
		return a.r < b.r;
}
int ans[maxn + 10];
unordered_map<int, int> cnt1;
void add(int p, int& ans) {
	cnt1[a[p]]++;
	if (cnt1[a[p]] > cnt1[ans])
		ans = a[p];
	else if (cnt1[a[p]] == cnt1[ans])
		ans = min(a[p], ans);
}
void del(int p) {
	cnt1[a[p]]--;
}
void solve() {
	int n;
	cin >> n;
	init(n);
	for (int i = 1; i <= n; i++) {
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	sort(q + 1, q + 1 + n, cmp);
	int l = 1, r = 0;
	int curblo = 0;
	int Max = 0;
	for (int i = 1; i <= n; i++) {
		if (bel[q[i].l] == bel[q[i].r]) {
			unordered_map<int, int> cnt2;
			for (int j = q[i].l; j <= q[i].r; j++)
				cnt2[a[j]]++;
			int t = 0;
			for (int j = q[i].l; j <= q[i].r; j++)
				if (cnt2[a[j]] > cnt2[t])
					t = a[j];
				else if (cnt2[a[j]] == cnt2[t])
					t = min(a[j], t);
			ans[q[i].id] = t;
			continue;
		}
		if (curblo != bel[q[i].l]) {
			while (r > ed[bel[q[i].l]])
				del(r--);
			while (l < ed[bel[q[i].l]] + 1)
				del(l++);
			Max = 0;
			curblo = bel[q[i].l];
		}
		while (r < q[i].r)
			add(++r, Max);
		int t = Max;
		int l2 = l;
		while (l2 > q[i].l)
			add(--l2, t);
		ans[q[i].id] = t;
		while (l2 < l)
			del(l2++);
	}
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << '\n';
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}