Code+ #1 Yazid的新生舞会

发表于 | 更新于 | 分类于 | 阅读次数：

Code+ #1 Yazid的新生舞会

Description

给定长度为$n (n \le 5 \times 10 ^ 5)$的序列，求满足区间$[l, r]$众数出现次数严格大于$\displaystyle \frac {r - l + 1} {2}$的子区间个数

Solution

考虑分治

对于$[L, R]$以及$Mid$，我们想办法统计经过$Mid$的区间的答案

首先求出所有可能的众数，这个可以$\mathcal{O} (n)$求出

然后将式子转化一下，枚举所有众数，设当前数为$x$
$$
cnt \gt \lfloor \frac {r - l + 1} {2} \rfloor
$$

$$
2cnt \gt r - l + 1
$$

可以将$cnt$拆成两部分
$$
2cnt_{L \sim r} - 2cnt_{L \sim {l - 1}} > r - L - (l - 1 - L)
$$

$$
cnt_{L \sim r} - (r - L + 1 - cnt_{L \sim r}) > cnt_{L \sim l - 1} - (l - 1 - L + 1 - cnt_{L \sim l - 1})
$$

发现不等号右边那个部分可以通过枚举$L \sim Mid$全部求出来，统计的时候求个前缀和即可

复杂度$\mathcal {O} (n \log ^ 2 n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long

inline int read() {
	int x = 0; char c = getchar();
	for (; c < 48 || c > 57; c = getchar());
	for (; c >= 48 && c <= 57; c = getchar()) x = x * 10 + (c ^ 48);
	return x;
}

const int N = 5e5;
int n, a[N + 5], cnt[N + N + 5];
LL ans;
bool vis[N + 5];
std::vector <int> Vec;

void Solve(int L, int R) {
	if (L == R) return (void) (++ans);
	int Mid = (L + R) >> 1;
	Solve(L, Mid);
	Solve(Mid + 1, R);
	for (int i = Mid; i >= L; --i)
		if (++cnt[a[i]] > (Mid - i + 1) / 2 && vis[a[i]] == false) {
			Vec.push_back(a[i]);
			vis[a[i]] = true;
		}
	for (int i = Mid + 1; i <= R; ++i)
		if (++cnt[a[i]] > (i - Mid) / 2 && vis[a[i]] == false) {
			Vec.push_back(a[i]);
			vis[a[i]] = true;
		}
	for (int i = L; i <= R; ++i) {
		cnt[a[i]] = 0;
		vis[a[i]] = false;
	}
	for (int x : Vec) {
		int tot = R - L + 1, Max = tot, Min = tot;
		cnt[tot] = 1;
		for (int i = L; i < Mid; ++i) {
			tot += a[i] == x ? 1 : -1;
			++cnt[tot];
			Max = std::max(Max, tot);
			Min = std::min(Min, tot);
		}
		tot += a[Mid] == x ? 1 : -1;
		for (int i = Min; i <= Max; ++i) cnt[i] += cnt[i - 1];
		for (int i = Mid + 1; i <= R; ++i) {
			tot += a[i] == x ? 1 : -1;
			ans += cnt[std::min(Max, tot - 1)];
		}
		for (int i = Min; i <= Max; ++i) cnt[i] = 0;
	}
	Vec.clear();
}

int main() {
	n = read(), read();
	for (int i = 1; i <= n; ++i)
		a[i] = read();
	Solve(1, n);
	printf("%lld\n", ans);
	return 0;
}