专栏文章

题解：SP9055 FREQ2 - Most Frequent Value

CCharllote_
SP9055题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipw1jdh
此快照首次捕获于
2025/12/03 18:52
3 个月前
此快照最后确认于
2025/12/03 18:52
3 个月前
查看原文

题解：SP9055 FREQ2 - Most Frequent Value

关于此题

首先我们看到这是一道 spoj 的题，这就注定了它是卡常的。发现这道题与蒲公英很像，然后就被卡常了。所以这道题不能用普通的分块做。

思路

说明 L(i)、R(i)、ID(i) 分别表示第 ii 块的左端点、右端点和第 ii 个数在那个块。

普通分块（TLE）

块长为 n\sqrt{n}。因为值域太大所以要进行离散化。
维护两个数组分别是 q[i][j] 和 md[i][j] 分别表示在前 ii 个块中值为 jj 的数出现的个数与在第 i∼ji \sim j 的块中的众数是谁。
我们发现在 l∼rl \sim r 中影响众数的地方在 l∼R(ID(l))l \sim R(ID(l))、L(ID(r))∼rL(ID(r)) \sim r。所以我们只要暴力枚举这两块直接的数，直接增加打擂台即可。
时间复杂度：Θ(nn)\Theta (n\sqrt{n})（常数过大）

莫队（AC）

发现这道题与蒲公英不同的地方在于：
  1. 它没有强制在线
  2. 它只需要求出现次数
所以考虑莫队。
同普通分块一样需要离散化，块长为 n\sqrt{n}。由于指针要来回跑所以要把查询按左端点所在的块排序，同一块内的查询按右端点排序。
使用两个指针 curl 和 curr 表示当前处理的区间。通过移动指针来调整当前区间，同时维护一个计数数组 cnt 和一个频率数组 freq。cnt[x] 表示当前区间中整数 x 的出现次数。freq[k] 表示当前区间中出现次数为 k 的整数的个数。
对于每个查询，通过移动指针 curl 和 curr 来调整当前区间，使其与查询区间一致。在移动指针的过程中，更新 cnt 和 freq 数组，并打擂台维护当前最大出现次数 current_max。
时间复杂度：Θ(nn)\Theta (n\sqrt{n})（常数小）

Code

普通分块（TLE）

CPP
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("1,2,3,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2,-ffast-math,-fsched-spec,unroll-loops,-falign-jumps,-falign-loops,-falign-labels,-fdevirtualize,-fcaller-saves,-fcrossjumping,-fthread-jumps,-fwhole-program,-freorder-blocks,-fschedule-insns,inline-functions,-ftree-tail-merge,-fschedule-insns2,-fstrict-aliasing,-fstrict-overflow,-falign-functions,-fcse-skip-blocks,-fcse-follow-jumps,-fsched-interblock,-fpartial-inlining,no-stack-protector,-freorder-functions,-findirect-inlining,-frerun-cse-after-loop,inline-small-functions,-ftree-switch-conversion,-foptimize-sibling-calls,-fexpensive-optimizations,-funsafe-loop-optimizations,inline-functions-called-once,-fdelete-null-pointer-checks")
#pragma G++ optimize("1,2,3,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2,-ffast-math,-fsched-spec,unroll-loops,-falign-jumps,-falign-loops,-falign-labels,-fdevirtualize,-fcaller-saves,-fcrossjumping,-fthread-jumps,-fwhole-program,-freorder-blocks,-fschedule-insns,inline-functions,-ftree-tail-merge,-fschedule-insns2,-fstrict-aliasing,-fstrict-overflow,-falign-functions,-fcse-skip-blocks,-fcse-follow-jumps,-fsched-interblock,-fpartial-inlining,no-stack-protector,-freorder-functions,-findirect-inlining,-frerun-cse-after-loop,inline-small-functions,-ftree-switch-conversion,-foptimize-sibling-calls,-fexpensive-optimizations,-funsafe-loop-optimizations,inline-functions-called-once,-fdelete-null-pointer-checks")

const int N = 1e5 + 5, SN = sqrt(N) + 5;
int n, m, len, a[N], q[SN][N], md[SN][SN], l, r, h[N], rl[N];

inline int ID(int x) { return (x - 1) / len + 1; }

inline int discrete(int (&a)[N], int n) {
	int b[n + 1];
	for (int i = 1; i <= n; i++) b[i] = a[i];
	sort(b + 1, b + n + 1);
	int m = unique(b + 1, b + n + 1) - b;
	for (int i = 1, x; i <= n; i++) {
		x = lower_bound(b + 1, b + m, a[i]) - b;
		rl[x] = a[i];
		a[i] = x;
	}
	return m;
}

inline int sum(int x, int y, int z) {
	return x <= y ? q[y][z] - q[x - 1][z] : 0;
}

inline int ask(int l, int r) {
	int ret = -1, retsum = -1;
	if (ID(l) == ID(r)) {
		for (int i = l; i <= r; i++) {
			if (++h[a[i]] > retsum || (h[a[i]] == retsum && rl[a[i]] < ret)) {
				ret = rl[a[i]];
				retsum = h[a[i]];
			}
		}
		for (int i = l; i <= r; i++) h[a[i]]--;
		return retsum;
	}
	int bl = ID(l) + 1, br = ID(r) - 1;
	int mode = bl <= br ? md[bl][br] : 0;
	retsum = sum(bl, br, mode);
	ret = mode ? rl[mode] : -1;

	for (int i = l; ID(i) == ID(l); i++) {
		int k = a[i];
		int cnt = sum(bl, br, k) + (++h[k]);
		if (cnt > retsum || (cnt == retsum && rl[k] < ret)) {
			ret = rl[k];
			retsum = cnt;
		}
	}
	for (int i = r; ID(i) == ID(r); i--) {
		int k = a[i];
		int cnt = sum(bl, br, k) + (++h[k]);
		if (cnt > retsum || (cnt == retsum && rl[k] < ret)) {
			ret = rl[k];
			retsum = cnt;
		}
	}
	for (int i = l; ID(i) == ID(l); i++) h[a[i]]--;
	for (int i = r; ID(i) == ID(r); i--) h[a[i]]--;
	return retsum;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;
	len = sqrt(n);

	for (int i = 1; i <= n; i++) cin >> a[i];
	int num = discrete(a, n);

	memset(q[0], 0, sizeof(q[0]));
	for (int i = 1; i <= n; i++) {
		if (ID(i) != ID(i - 1)) memcpy(q[ID(i)], q[ID(i) - 1], sizeof(q[0]));
		q[ID(i)][a[i]]++;
	}

	for (int i = 1; i <= ID(n); i++) {
		for (int j = i; j <= ID(n); j++) {
			if (j == i) {
				int max_cnt = -1, mode = 0;
				for (int k = 1; k <= num; k++) {
					int cnt = sum(i, j, k);
					if (cnt > max_cnt || (cnt == max_cnt && k < mode)) {
						max_cnt = cnt;
						mode = k;
					}
				}
				md[i][j] = mode;
			} else {
				md[i][j] = md[i][j - 1];
				int current_max = sum(i, j, md[i][j]);
				for (int k = 1; k <= num; k++) {
					int cnt = sum(i, j, k);
					if (cnt > current_max ||
						(cnt == current_max && k < md[i][j])) {
						current_max = cnt;
						md[i][j] = k;
					}
				}
			}
		}
	}

	while (m--) {
		cin >> l >> r;
		cout << ask(l + 1, r + 1) << '\n';
	}

	return 0;
}

莫队（AC）

CPP
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;

int n, q, block_size;
int a[MAXN], ans[MAXN];
int cnt[MAXN], freq[MAXN], current_max;

struct Query {
	int l, r, idx;
	bool operator<(const Query& other) const {
		if (l / block_size != other.l / block_size)
			return l < other.l;
		else {
			if ((l / block_size) % 2 == 0)
				return r < other.r;
			else
				return r > other.r;
		}
	}
} queries[MAXN];

void add(int x) {
	freq[cnt[x]]--;
	cnt[x]++;
	freq[cnt[x]]++;
	if (cnt[x] > current_max) current_max = cnt[x];
}

void remove(int x) {
	freq[cnt[x]]--;
	cnt[x]--;
	freq[cnt[x]]++;
	if (freq[current_max] == 0) current_max--;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> q;
	vector<int> temp(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		temp[i] = a[i];
	}

	// 离散化处理
	sort(temp.begin(), temp.end());
	temp.erase(unique(temp.begin(), temp.end()), temp.end());
	for (int i = 0; i < n; ++i)
		a[i] = lower_bound(temp.begin(), temp.end(), a[i]) - temp.begin() + 1;

	// 读取查询
	for (int i = 0; i < q; ++i) {
		int l, r;
		cin >> l >> r;
		queries[i].l = l;
		queries[i].r = r;
		queries[i].idx = i;
	}

	// 设置块大小并排序查询
	block_size = sqrt(n) + 1;
	sort(queries, queries + q);

	// 初始化
	current_max = 0;
	memset(cnt, 0, sizeof(cnt));
	memset(freq, 0, sizeof(freq));
	int cur_l = 0, cur_r = -1;

	for (int i = 0; i < q; ++i) {
		int l = queries[i].l;
		int r = queries[i].r;

		while (cur_l > l) add(a[--cur_l]);
		while (cur_r < r) add(a[++cur_r]);
		while (cur_l < l) remove(a[cur_l++]);
		while (cur_r > r) remove(a[cur_r--]);

		ans[queries[i].idx] = current_max;
	}

	for (int i = 0; i < q; ++i) cout << ans[i] << '\n';

	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...