「BZOJ 2038」小Z的袜子

题目地址

描述

作为一个生活散漫的人,小Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……
具体来说,小Z 把这 $N( 1\leq N \leq 500000)$ 只袜子从 $1$ 到 $N$ 编号,然后从编号 $L$ 到 $R$ 。尽管小 Z 并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉 小Z,他有多大的概率抽到两只颜色相同的袜子。当然,小 Z 希望这个概率尽量高,所以他可能会询问多个 $(L,R)$ 以方便自己选择。

分析

我们可以把答案表示为

其中 $cnt[i]$ 为颜色 $i$ 的个数,$c[i]$ 为 $i$ 的颜色,$a[i]$ 为原颜色序列 $a$ 第 $i$ 位的颜色,我们可以将原式化简一下,变为 :

这样一来,单个数字对答案的贡献可以简化为

每加进来或删去一个数字时,可以 $\Theta(1)$ 重新计算单个数字对答案的贡献来得到新区间的答案。

代码

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
//  Created by ZJYelizaveta on 2017年09月03日 星期日 09时44分10秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 50000 + 3;
const int INF = 0x3f3f3f3f;
int n, m;
int a[MAX_N];
struct Interval {
int l, r, id, pos;
bool operator < (const Interval &rhs) const {
if (pos == rhs.pos) return r < rhs.r;
return pos < rhs.pos;
}
}q[MAX_N];
ll cnt[MAX_N], ans[MAX_N][2], res;
int blockSize, f[MAX_N];

inline ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}

inline void modify(int id, int w) {
res += (ll)2 * cnt[a[id]] * w + 1;
cnt[a[id]] += w;
}

inline void solve() {
memset(cnt, 0, sizeof cnt);
int l = 1, r = 0; res = 0;
for (int i = 1; i <= m; ++i) {
const Interval &b = q[i];
while (b.l < l) {--l; modify(l, 1);}
while (r < b.r) {++r; modify(r, 1);}
while (l < b.l) {modify(l, -1); ++l;}
while (b.r < r) {modify(r, -1); --r;}
if (b.l == b.r) {ans[i][0] = 0; ans[i][1] = 1; continue;}
ans[i][0] = (ll)res - (b.r - b.l + 1); ans[i][1] = (ll)(b.r - b.l + 1) * (b.r - b.l);
ll cur = gcd(ans[i][0], ans[i][1]);
ans[i][0] = ans[i][0] / cur, ans[i][1] = ans[i][1] / cur;
f[b.id] = i;
}
}

int main()
{
n = readIn(), m = readIn();
blockSize = (int)(sqrt(n));
for (int i = 1; i <= n; ++i) a[i] = readIn();
for (int i = 1; i <= m; ++i) {
q[i].l = readIn(), q[i].r = readIn(), q[i].id = i;
q[i].pos = (q[i].l - 1) / blockSize + 1;
}
sort(q + 1, q + m + 1);
solve();
for (int i = 1; i <= m; ++i) printf("%lld/%lld\n", ans[f[i]][0], ans[f[i]][1]);
return 0;
}
Partager