专栏文章

题解：P13984 数列分块入门 9

ffzs7
P13984题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minychjo
此快照首次捕获于
2025/12/02 10:21
3 个月前
此快照最后确认于
2025/12/02 10:21
3 个月前
查看原文
一般来说维护这类神奇东西的题目都可以用莫队来做。
不会莫队的可以去 OI Wiki 上看看。
考虑莫队，加入一个数的时候应该怎么做。
设 cnticnt_i 表示当前区间内值为 ii 的数的个数，每次新加入一个元素就在对应的位置上加一，然后和原先答案取更优解就好了。
那删除呢？
当然，一种比较简单的思路是直接用回滚莫队，完全没有思维难度，这里介绍另一种方法——值域分块。
我们对值域进行分块，记 mximx_i 表示第 ii 个值域块里出现次数最多的值的出现次数，记 buci,jbuc_{i,j} 表示第 ii 个值域块里出现次数为 jj 的值的个数，每次加入和删除时在数组上进行相应更新，删除时若此时答案为 xx，xx所在块为 kxkx，若删除后 buckx,x=0buc_{kx,x}=0 那么就要将答案减一(这里答案指最小众数的出现次数)。
然后得到了最小众数的出现次数后，要得到最小众数，我们先对每个值域块扫过去，取 mximx_i 与答案相等的块，然后在块内元素找 cnticnt_i 与求得的值相等的数即为最终答案。
Code\large{Code}
CPP
//码风略丑，谨慎观看
#include <bits/stdc++.h>
using namespace std;

inline long long read(void) {
	long long x = 0, f = 1; char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - 48, c = getchar();
	return x * f;
}

struct node {
	long long l, r, id;
} query[300005];

long long n, k = 600, cl = 1, cr = 0, qwq[300005], a[300005], s[300005], ans[300005], buc1[1000], buc2[300005], buc3[505][300005], cnt;
map<long long, long long> mp;

bool cmp (node x, node y) {
	if (qwq[x. l] == qwq[y. l]) return (qwq[x. l] & 1) ? (x. r < y. r) : (x. r > y. r);
	return x. l < y. l;
}

int main(void) {
	n = read();
	for (int i = 1; i <= 300000; i++) qwq[i] = (i - 1) / k + 1;
	for (int i = 1; i <= n; i++) a[i] = s[i] = read();
	sort(s + 1, s + 1 + n);
	for (int i = 1; i <= n; i++) if (!mp[s[i]]) mp[s[i]] = ++cnt, s[cnt] = s[i];
	for (int i = 1; i <= n; i++) a[i] = mp[a[i]];
	for (int i = 1; i <= n; i++) query[i]. l = read(), query[i]. r = read(), query[i]. id = i;
	sort(query + 1, query + 1 + n, cmp);
	for (int i = 1; i <= n; i++) {
		while (cr < query[i]. r) {
			cr++;
			buc3[qwq[a[cr]]][buc2[a[cr]]]--;
			buc2[a[cr]]++;
			buc3[qwq[a[cr]]][buc2[a[cr]]]++;
			buc1[qwq[a[cr]]] = max(buc1[qwq[a[cr]]], buc2[a[cr]]);
		}
		while (cl > query[i]. l) {
			cl--;
			buc3[qwq[a[cl]]][buc2[a[cl]]]--;
			buc2[a[cl]]++;
			buc3[qwq[a[cl]]][buc2[a[cl]]]++;
			buc1[qwq[a[cl]]] = max(buc1[qwq[a[cl]]], buc2[a[cl]]);
		}
		while (cl < query[i]. l) {
			if (buc1[qwq[a[cl]]] == buc2[a[cl]] && buc3[qwq[a[cl]]][buc2[a[cl]]] == 1) buc1[qwq[a[cl]]]--;
			buc3[qwq[a[cl]]][buc2[a[cl]]]--;
			buc2[a[cl]]--;
			buc3[qwq[a[cl]]][buc2[a[cl]]]++;
			cl++;
		}
		while (cr > query[i]. r) {
			if (buc1[qwq[a[cr]]] == buc2[a[cr]] && buc3[qwq[a[cr]]][buc2[a[cr]]] == 1) buc1[qwq[a[cr]]]--;
			buc3[qwq[a[cr]]][buc2[a[cr]]]--;
			buc2[a[cr]]--;
			buc3[qwq[a[cr]]][buc2[a[cr]]]++;
			cr--;
		}
		long long nnn = 1;
		for (int j = 2; j <= qwq[300000]; j++) if (buc1[j] > buc1[nnn]) nnn = j;
		for (int j = (nnn - 1) * k + 1; j <= nnn * k; j++)
			if (buc2[j] == buc1[nnn]) {
				ans[query[i]. id] = j;
				break;
			}
	}
	for (int i = 1; i <= n; i++) printf("%lld\n", s[ans[i]]);
	return 0;
}

评论

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

正在加载评论...