专栏文章

カノジョの妹とキスをした。

冷冷却心月明かり
P14558题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min0wv5z
此快照首次捕获于
2025/12/01 18:45
3 个月前
此快照最后确认于
2025/12/01 18:45
3 个月前
查看原文
引理：给定序列 a1,a2,…,ana_1,a_2,\dots,a_n，对于所有存在绝对众数的前缀，绝对众数的种类数 O(log⁡n)O(\log n)。
证明：我们记 cic_i 表示从前往后出现的第 ii 种绝对众数在第一次成为绝对众数时在前缀中的出现次数，显然有 ci>ci−1>ci−2c_i>c_{i-1}>c_{i-2}，但是他所在的前缀也包含了 i−1,i−2i-1,i-2 两种绝对众数，所以需要满足 ci>ci−1+ci−2>2ci−2c_i>c_{i-1}+c_{i-2}>2c_{i-2}，我们只考虑下标为奇数的子序列 c2k+1c_{2k+1}，有 c2k+1>2c2k−1c_{2k+1}>2c_{2k-1}，由于最后一项应当小于等于 nn，所以子序列长度至多 log⁡n\log n，cc 的长度也至多 2log⁡n2\log n。
考虑分治，对于一个跨越分治中心 pp 的区间 [l,r][l,r]，考虑摩尔投票，如果他有绝对众数，一定是 [l,p][l,p] 做摩尔投票得到的众数或者 [p+1,r][p+1,r] 做摩尔投票得到的绝对众数。根据引理，所有 [l,p][l,p] 的绝对众数和所有 [p+1,r][p+1,r] 的绝对众数的种类只有 O(log⁡n)O(\log n)，所以我们只讨论这 O(log⁡n)O(\log n) 种数在哪些跨越中心的区间成为了绝对众数即可。设当前考虑 xx 是否能成为绝对众数，合法当且仅当区间内 xx 个数大于非 xx 的个数，即区间 xx 个数减去非 xx 个数大于 00。记 srs_r 表示 [p+1,r][p+1,r] 区间内 xx 个数减去非 xx 个数，tlt_l 表示 [l,p][l,p] 区间内 xx 个数减去非 xx 个数，区间 [l,r][l,r] 合法当且仅当 tl+sr>0t_l+s_r>0，枚举 rr，相当于求出满足 tl>−srt_l>-s_r 的 ll 个数，由于 tt 的值域 O(n)O(n)，可以直接开桶计数做到 O(n)O(n)。每层有 O(log⁡n)O(\log n) 种众数故做 O(log⁡n)O(\log n) 次，一共有 log⁡n\log n 层，复杂度 2log。
判断一个数是否是一个区间的绝对众数只需要统计他在区间内出现了几次，对出现的所有数开 vector 记录出现的位置，二分查找即可求出。
CPP
#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 1e6 + 10;
int n, m, A[N];

vector<int> vec[N]; unordered_map<int, int> idx;

bool check(int l, int r, int k) {
	k = idx[k];
	return 2 * (upper_bound(vec[k].begin(), vec[k].end(), r) - lower_bound(vec[k].begin(), vec[k].end(), l)) > r - l + 1;
}

LL Ans = 0; int cnt[N];
void Solve(int l, int r) {
	if (l == r) { ++ Ans; return ; }
	int mid = (l + r) >> 1;
	vector<int> key;
	for (int i = mid, t = 0, c = 0; i >= l; i --) {
		if (!c) t = A[i], c = 1;
		else c += (t == A[i] ? 1 : -1);
		if (check(i, mid, t)) key.push_back(t); 
	}
	for (int i = mid + 1, t = 0, c = 0; i <= r; i ++) {
		if (!c) t = A[i], c = 1;
		else c += (t == A[i] ? 1 : -1);
		if (check(mid + 1, i, t)) key.push_back(t); 
	}
	sort(key.begin(), key.end()); key.erase(unique(key.begin(), key.end()), key.end());
	for (int x : key) {
		int lim = (r - l + 1) / 2 + 5;
		for (int i = mid, c = 0; i >= l; i --) {
			c += (A[i] == x ? 1 : -1);
			cnt[c + lim] ++;
		}
		for (int i = lim * 2; i >= 0; i --) cnt[i] += cnt[i + 1];
		for (int i = mid + 1, c = 0; i <= r; i ++) {
			c += (A[i] == x ? 1 : -1); Ans += cnt[lim - c + 1];
		}
		for (int i = 0; i <= lim * 2; i ++) cnt[i] = 0;
	}
	Solve(l, mid), Solve(mid + 1, r);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) cin >> A[i], idx[A[i]] = i;
	for (int i = 1; i <= n; i ++) vec[idx[A[i]]].push_back(i);
	Solve(1, n);
	cout << Ans << "\n";
	return 0;
}

评论

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

正在加载评论...