🦄️🦄️ Horse Power! ️🦄️🦄️

0%

「Codechef SEAARC」Sereja And Arcs（数据分治）

发表于 Valine：

题目描述

「Codechef SEAARC」Sereja and Arcs

数轴上有 $n$ 个点，坐标为 $1, 2, \cdots n$。每个点有个颜色，颜色相同的点两两之间会连一条与经过数轴上方的半圆形圆弧，颜色和端点一样。问共有多少对不同色圆弧相交，答案对大素数取模。

数据范围：$n \le 10^5$。

思路分析

考虑设定阀值 $b$，对于出现次数不超过 $b$ 的颜色，我们暴力地把每条圆弧拿出来，用树状数组来计算有多少对相交；对于剩下的颜色，我们 $O(n)$ 地计算它与剩下所有颜色圆弧的交点个数（这部分可以 dp，具体见代码）。这样总共的复杂度为 $O(nb \log {nb} + \frac{n^2}{b})$，取 $b = 100$ 即可通过。

代码实现

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
using namespace std;

namespace __main__ {
	typedef long long ll;
	const int maxn = 1e5, b = 100, mod = 1e9 + 7;
	int n, a[maxn + 3], prev[maxn + 3], last[maxn + 3];
	int cnt[maxn + 3], bit[maxn + 3], type[maxn + 3], m, temp[maxn + 3];
	int cur[maxn + 3], f[maxn + 3], g[maxn + 3], h[maxn + 3], id[maxn + 3];

	void add(int x, int y) {
		for (int i = x; i; i ^= i & -i) {
			bit[i] += y;
		}
	}

	int sum(int x) {
		int y = 0;
		for (int i = x; i <= n; i += i & -i) {
			y += bit[i];
		}
		return y;
	}

	ll solve() {
		ll ans = 0;
		for (int i = 1; i <= n; i++) {
			if (type[a[i]] == 0) {
				for (int j = prev[i]; j; j = prev[j]) {
					add(i, 1), add(j - 1, -1);
				}
				for (int j = prev[i]; j; j = prev[j]) {
					ans += sum(j);
				}
			}
		}
		memset(bit, 0, sizeof(bit));
		for (int i = 1; i <= maxn; i++) {
			if (type[i] == 0 && last[i]) {
				m = 0;
				for (int j = last[i]; j; j = prev[j]) {
					temp[++m] = j;
				}
				reverse(temp + 1, temp + m + 1);
				for (int j = 1; j <= m; j++) {
					for (int k = prev[temp[j]]; k; k = prev[k]) {
						add(temp[j], 1), add(k - 1, -1);
					}
					for (int k = prev[temp[j]]; k; k = prev[k]) {
						ans -= sum(k);
					}
				}
				for (int j = 1; j <= m; j++) {
					for (int k = prev[temp[j]]; k; k = prev[k]) {
						add(temp[j], -1), add(k - 1, 1);
					}
				}
			}
		}
		return ans;
	}

	inline int func(int x) {
		return x < mod ? x : x - mod;
	}

	int calc(int x) {
		int ans = 0, cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i] == x) {
				cnt++;
			} else if (cur[a[i]] == 0) {
				id[i] = cnt;
			}
		}
		for (int i = 1; i <= n; i++) {
			if (cur[a[i]] == 0) {
				if (!prev[i]) {
					f[i] = 1, g[i] = h[i] = 0;
				} else {
					int d = id[i] - id[prev[i]], p = prev[i];
					f[i] = f[p] + 1;
					g[i] = (g[p] + 1ll * f[p] * d) % mod;
					h[i] = (h[p] + 2ll * g[p] * d + 1ll * f[p] * d % mod * d) % mod;
					ans = (ans + 1ll * g[i] * cnt) % mod;
					ans = func(ans - h[i] + mod);
				} 
			}
		}
		return ans;
	}

	void main() {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]), cnt[a[i]]++;
			prev[i] = last[a[i]], last[a[i]] = i;
		}
		for (int i = 1; i <= maxn; i++) {
			type[i] = cnt[i] >= b;
		}
		int ans = solve() % mod;
		memcpy(cur, type, sizeof(cur));
		for (int i = 1; i <= maxn; i++) {
			if (type[i] == 1) {
				ans = func(ans + calc(i));
				cur[i] = 0;
			}
		}
		printf("%d\n", ans);
	}
}

int main() {
	__main__::main();
	return 0;
}