题面

Yuno loves sqrt technology III

题解

一道很水的黑题。
做过蒲公英的同学应该都知道这和蒲公英很类似。
不同的是它维护的是区间众数的个数。
因为区间众数不具有可加性，再加上强制在线，显然是用分块来维护。
首先正常分块。
预处理块内信息时的整合就直接 \(\sqrt(n) ^ 3\) 暴力枚举，得到块 \(l\) 到 块 \(r\) 的区间众数个数。
对于询问就和正常分块相同，暴力处理两边零散的情况。
但不同于蒲公英的是，这道题数据范围更大些，再加一个 \(logn\) 的二分查找，显然是不行的。
所以我们需要找到一个更快的处理方法。
记录 \(a[i]\) 在数值 \(a[i]\) 中的次序 \(it\)， 以及每个 \(a[i]\) 出现的位置。
首先用 \(ans\) 记录整块区间的信息。
对于左边零散的部分：
如果 \(it + ans - 1 < a[i]的总个数\)，那么显然 \(a[i]\) 是有可能更新答案的，那么我们再看 \(it + ans - 1\) 这个次序的 \(a[i]\) 出现的位置是否在我们询问的边界 \(r\) 内，如果是，就说明 \(a[i]\) 在 \(r\) 内是至少有 \(ans + 1\) 个答案的。所以我们就直接更新答案就是了。
对于右边零散的部分同理,只需要判断位置是否在左边界内就行了，具体细节请看码。

代码

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>

using namespace std;

const int N = 5e5 + 10, M = 710;

int n, m, a[N], b[N], len = 0, tot[N], block, L[M], R[M], Max[M][M], ans = 0, bel[N], cnt[N];

vector < int > pos[N];

inline int query(int l, int r) {
	int p = bel[l], q = bel[r], ans = 0;
	if(p == q) {
		for(int i = l; i <= r; i++) tot[a[i]] = 0;
		for(int i = l; i <= r; i++)
			ans = max(ans, ++tot[a[i]]);
	}
	else {
		ans = Max[p + 1][q - 1];
		for(int i = l; i <= R[p]; i++) {
			int it = cnt[i]; while(it + ans < pos[a[i]].size() && pos[a[i]][it + ans] <= r) ++ans;
		}
		for(int i = L[q]; i <= r; i++) {
			int it = cnt[i]; while(it - ans >= 0 && pos[a[i]][it - ans] >= l) ++ans;
		}
	}
	return ans;
}

inline void read(int &x) {
	x = 0; int f = 1, c = getchar();
	for(; !isdigit(c); c = getchar())
		if(c == '-')
			f = -1;
	for(; isdigit(c); c = getchar())
		x = x * 10 + c - 48;
	x *= f;
}

int main() {
	read(n), read(m);
	for(int i = 1; i <= n; i++) read(a[i]), b[i] = a[i];
	sort(b + 1, b + 1 + n);
	len = unique(b + 1, b + 1 + n) - b - 1;
	for(int i = 1; i <= n; i++)
		a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b,
		pos[a[i]].push_back(i), cnt[i] = pos[a[i]].size() - 1;
	block = sqrt(n);
	for(int i = 1; i <= block; i++)
		L[i] = (i - 1) * block + 1,
		R[i] = i * block;
	if(R[block] < n) block++, L[block] = R[block - 1] + 1, R[block] = n;
	for(int i = 1; i <= block; i++)
		for(int j = L[i]; j <= R[i]; j++)
			bel[j] = i;
	for(int l = 1; l <= block; l++) {
		memset(tot, 0, sizeof tot);
		for(int r = l; r <= block; r++) {
			Max[l][r] = Max[l][r - 1];
			for(int j = L[r]; j <= R[r]; j++)
				Max[l][r] = max(Max[l][r], ++tot[a[j]]);
		}
	}
	for(int i = 1, l, r; i <= m; i++) {
		read(l), read(r);
		l ^= ans, r ^= ans;
		if(l > r) swap(l, r);
		printf("%d\n", ans = query(l, r));
	}
	return 0;
}