题目描述
「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 | using namespace std; |
3 | |
4 | namespace __main__ { |
5 | typedef long long ll; |
6 | const int maxn = 1e5, b = 100, mod = 1e9 + 7; |
7 | int n, a[maxn + 3], prev[maxn + 3], last[maxn + 3]; |
8 | int cnt[maxn + 3], bit[maxn + 3], type[maxn + 3], m, temp[maxn + 3]; |
9 | int cur[maxn + 3], f[maxn + 3], g[maxn + 3], h[maxn + 3], id[maxn + 3]; |
10 | |
11 | void add(int x, int y) { |
12 | for (int i = x; i; i ^= i & -i) { |
13 | bit[i] += y; |
14 | } |
15 | } |
16 | |
17 | int sum(int x) { |
18 | int y = 0; |
19 | for (int i = x; i <= n; i += i & -i) { |
20 | y += bit[i]; |
21 | } |
22 | return y; |
23 | } |
24 | |
25 | ll solve() { |
26 | ll ans = 0; |
27 | for (int i = 1; i <= n; i++) { |
28 | if (type[a[i]] == 0) { |
29 | for (int j = prev[i]; j; j = prev[j]) { |
30 | add(i, 1), add(j - 1, -1); |
31 | } |
32 | for (int j = prev[i]; j; j = prev[j]) { |
33 | ans += sum(j); |
34 | } |
35 | } |
36 | } |
37 | memset(bit, 0, sizeof(bit)); |
38 | for (int i = 1; i <= maxn; i++) { |
39 | if (type[i] == 0 && last[i]) { |
40 | m = 0; |
41 | for (int j = last[i]; j; j = prev[j]) { |
42 | temp[++m] = j; |
43 | } |
44 | reverse(temp + 1, temp + m + 1); |
45 | for (int j = 1; j <= m; j++) { |
46 | for (int k = prev[temp[j]]; k; k = prev[k]) { |
47 | add(temp[j], 1), add(k - 1, -1); |
48 | } |
49 | for (int k = prev[temp[j]]; k; k = prev[k]) { |
50 | ans -= sum(k); |
51 | } |
52 | } |
53 | for (int j = 1; j <= m; j++) { |
54 | for (int k = prev[temp[j]]; k; k = prev[k]) { |
55 | add(temp[j], -1), add(k - 1, 1); |
56 | } |
57 | } |
58 | } |
59 | } |
60 | return ans; |
61 | } |
62 | |
63 | inline int func(int x) { |
64 | return x < mod ? x : x - mod; |
65 | } |
66 | |
67 | int calc(int x) { |
68 | int ans = 0, cnt = 0; |
69 | for (int i = 1; i <= n; i++) { |
70 | if (a[i] == x) { |
71 | cnt++; |
72 | } else if (cur[a[i]] == 0) { |
73 | id[i] = cnt; |
74 | } |
75 | } |
76 | for (int i = 1; i <= n; i++) { |
77 | if (cur[a[i]] == 0) { |
78 | if (!prev[i]) { |
79 | f[i] = 1, g[i] = h[i] = 0; |
80 | } else { |
81 | int d = id[i] - id[prev[i]], p = prev[i]; |
82 | f[i] = f[p] + 1; |
83 | g[i] = (g[p] + 1ll * f[p] * d) % mod; |
84 | h[i] = (h[p] + 2ll * g[p] * d + 1ll * f[p] * d % mod * d) % mod; |
85 | ans = (ans + 1ll * g[i] * cnt) % mod; |
86 | ans = func(ans - h[i] + mod); |
87 | } |
88 | } |
89 | } |
90 | return ans; |
91 | } |
92 | |
93 | void main() { |
94 | scanf("%d", &n); |
95 | for (int i = 1; i <= n; i++) { |
96 | scanf("%d", &a[i]), cnt[a[i]]++; |
97 | prev[i] = last[a[i]], last[a[i]] = i; |
98 | } |
99 | for (int i = 1; i <= maxn; i++) { |
100 | type[i] = cnt[i] >= b; |
101 | } |
102 | int ans = solve() % mod; |
103 | memcpy(cur, type, sizeof(cur)); |
104 | for (int i = 1; i <= maxn; i++) { |
105 | if (type[i] == 1) { |
106 | ans = func(ans + calc(i)); |
107 | cur[i] = 0; |
108 | } |
109 | } |
110 | printf("%d\n", ans); |
111 | } |
112 | } |
113 | |
114 | int main() { |
115 | __main__::main(); |
116 | return 0; |
117 | } |