P1494「[国家集训队]小Z的袜子」

1. 题目

题目链接:P1494「[国家集训队]小Z的袜子」

题目描述

作为一个生活散漫的人,小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小 Z 再也无法忍受这恼人的找袜子过程,于是他决定听天由命……

具体来说,小 Z 把这 NN 只袜子从 11NN 编号,然后从编号 LLRR (尽管小 Z 并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬)。

你的任务便是告诉小 Z,他有多大的概率抽到两只颜色相同的袜子。当然,小 Z 希望这个概率尽量高,所以他可能会询问多个 (L,R)(L,R) 以方便自己选择。

然而数据中有 L=RL=R 的情况,请特判这种情况,输出 0/10/1

输入格式

输入文件第一行包含两个正整数 NNMMNN 为袜子的数量,MM 为小 Z 所提的询问的数量。接下来一行包含 NN 个正整数 CiC_i,其中 CiC_i,表示第 ii 只袜子的颜色,相同的颜色用相同的数字表示。再接下来 MM 行,每行两个正整数 L,RL,R 表示一个询问。

输出格式

包含 MM 行,对于每个询问在一行中输出分数 A/BA/B 表示从该询问的区间 [L,R][L,R] 中随机抽出两只袜子颜色相同的概率。若该概率为 00 则输出 0/10/1,否则输出的 A/BA/B 必须为最简分数。(详见样例)

输入输出样例

输入 #1

1
2
3
4
5
6
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

输出 #1

1
2
3
4
2/5
0/1
1/1
4/15

说明/提示

30%30\% 的数据中,N,M5000N,M \leq 5000

60%60\% 的数据中,N,M25000N,M \leq 25000

100%100\% 的数据中,N,M50000N,M \leq 500001L<RN1 \leq L < R \leq NCiNC_i \leq N

2. 题解

分析

一看题目,可以离线查询,而且 O(mn)O(m \sqrt{n}) 的时间复杂度可以过,那么可以考虑用莫队算法。

假设袜子总数为 nncolor[i]color[i] 表示第 ii 个位置的袜子颜色。

  • 考虑由区间 [l,r][l,r] 转移到区间 [l,r+1][l,r+1](其它三个相邻区间分析类似),设 [l,r][l,r] 中颜色相同的两只袜子的配对数为 ansl,rans_{l,r}count[j]count[j] 表示区间 [l,r][l,r] 中颜色为 jj 的袜子数目,则由排列组合可知

x=count[color[r+1]]y=count[color[r+1]]+1ansl,r+1=ansl,r+(Cy2Cx2)=ansl,r+count[color[r+1]]{\begin{array}{rl} x &= count[color[r+1]] \\ y &= count[color[r+1]]+1 \\ ans_{l,r+1} &= ans_{l,r} + (C_{y}^2 - C_{x}^2) \\ &= ans_{l,r} + count[color[r+1]] \end{array}}

因此,由区间 [l,r][l,r] 转移到其相邻的区间的时间复杂度为 O(1)O(1),故可以使用莫队算法。

  • 已知区间 [l,r][l,r] 中颜色相同的两只袜子的配对数为 ansl,rans_{l,r},则答案为 ansl,r/Crl+12ans_{l,r} / C_{r-l+1}^2。由于要求最简分数,因此可以使用辗转相除法计算分子和分母的最大公因数 d=gcd(ansl,r,Crl+12)d = gcd(ans_{l,r}, C_{r-l+1}^2),最终答案为 ansl,rd/Crl+12d\frac{ans_{l,r}}{d} / \frac{C_{r-l+1}^2}{d}

代码

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
#include <bits/stdc++.h>
#define ll int
#define MAXN 100000
using namespace std;

ll cnt[MAXN];

// 辗转相除法
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a%b);
}

ll bz; // 分块大小

// 莫队
struct MO {
// 查询区间
struct Query {
ll l, r;
ll idx, ntr, dtr;
bool operator < (Query q) const {
return l/bz != q.l/bz ? l < q.l :
(l/bz) & 1 ? r < q.r : r > q.r;
}
};
ll n, m; // 数列长度,查询次数
ll ans; // 查询答案
ll color[MAXN]; // 颜色数组
ll result[MAXN][2]; // 答案数组
Query query[MAXN]; // 查询区间数组
// 初始化
MO() {
ans = 0;
memset(query, 0, sizeof(query));
}
// 区间长度增一
void add(ll col) {
++cnt[col];
ans += cnt[col] - 1;
}
// 区间长度减一
void del(ll col) {
ans -= cnt[col] - 1;
--cnt[col];
}
// 求解答案
void solver() {
sort(query, query+m);
ll l = query[0].l;
ll r = query[0].l-1;
for(ll i = 0; i < m; ++i) {
if(query[i].l >= query[i].r) {
query[i].ntr = 0;
query[i].dtr = 1;
continue;
}
while(r < query[i].r) {
add(color[++r]);
}
while(r > query[i].r) {
del(color[r--]);
}
while(l < query[i].l) {
del(color[l++]);
}
while(l > query[i].l) {
add(color[--l]);
}
if(!ans) {
query[i].ntr = 0;
query[i].dtr = 1;
} else {
ll s = (r-l)%2 ? (r-l+1)/2*(r-l) : (r-l)/2*(r-l+1);
ll d = gcd(ans, s);
query[i].ntr = ans / d;
query[i].dtr = s / d;
}
}
for(ll i = 0; i < m; ++i) {
result[query[i].idx][0] = query[i].ntr;
result[query[i].idx][1] = query[i].dtr;
}
for(ll i = 0; i < m; ++i) {
printf("%d/%d\n", result[i][0], result[i][1]);
}
}
};

int main()
{
MO z;
scanf("%d%d", &z.n, &z.m);
bz = (int)sqrt(z.n);
for(ll i = 0; i < z.n; ++i) {
scanf("%d", &z.color[i]);
}
ll l, r;
for(ll i = 0; i < z.m; ++i) {
scanf("%d%d", &l, &r);
z.query[i].l = l-1;
z.query[i].r = r-1;
z.query[i].idx = i;
}
z.solver();
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!