AK-dream

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

【输入格式】
输入文件第一行包含两个正整数$N$和$M$。$N$为袜子的数量,$M$为小Z所提的询问的数量。接下来一行包含$N$个正整数$C_i$,其中$C_i$表示第$i$只袜子的颜色,相同的颜色用相同的数字表示。再接下来$M$行,每行两个正整数$L,R$表示一个询问。

【输出格式】
包含 $M$ 行,对于每个询问在一行中输出分数 $A/B$ 表示从该询问的区间 $[L,R]$ 中随机抽出两只袜子颜色相同的概率。若该概率为 $0$ 则输出 $0/1$,否则输出的 $A/B$ 必须为最简分数。

题解

莫队算法,简单来说就是暴力维护双指针指向当前查询区间的左右端点 每次左或右指针可以向左或向右移动一格 同时更新当前区间的答案

我们通过离线处理 给询问排序 如果直接先按询问左端点排再按右端点排 依然容易被卡掉

比如询问$[2,2],[3,1000],[4,4],[5,2000],[6,6]$ 如果按照$[2,2],[4,4],[6,6],[3,1000],[5,2000]$的顺序查询 显然右指针会少移动很多次

所以这个暴力的思路就是给左端点分块 左端点在同一个$\sqrt{n}$块中的询问优先按右端点排序 否则才是优先按左端点排序

这样做每一次左右指针只会移动大概$\sqrt{n}$次 这个复杂度是大约$O(q\sqrt{n})$的 足以通过此题

还有一种对询问排序的方法叫做什么奇偶块优化 似乎还要更快 可以背下板子

至于这道题具体怎么做。。。假设要加入一个颜色$x$ 加入后当前区间有$cnt[x]$个颜色$x$ 那么合法答案数就加上$cnt[x]-1$
如果移除一个颜色$x$ 那么就减去$cnt[x]$

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll read() {
ll x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
return x * f;
}

struct query{
ll l, r, id;
} q[50005];

ll n, m, bl;
ll c[50005];
ll cnt[50005], ans, nl, nr;
ll ansx[50005], ansy[50005];

inline bool cmp(query a, query b) { //奇偶块排序
if (a.l / bl == b.l / bl) {
if ((a.l / bl) & 1) return a.r > b.r;
else return a.r < b.r;
} else return a.l < b.l;
}

inline bool cmp2(query a, query b) { //普通按块排序
if (a.l / bl == b.l / bl) {
return a.r < b.r;
} else return a.l < b.l;
}

inline void add(ll x) {
cnt[x]++;
if (cnt[x] > 1) ans = ans + (cnt[x]-1);
}

inline void del(ll x) {
cnt[x]--;
if (cnt[x] > 0) ans = ans - cnt[x];
}

inline void update(ll l, ll r) {
while (nl < l) del(c[nl++]);
while (nl > l) add(c[--nl]);
while (nr < r) add(c[++nr]);
while (nr > r) del(c[nr--]);
}

inline void getans(ll x, ll y, ll id) {
if (x == 0) {
ansx[id] = 0; ansy[id] = 1;
return;
}
ll gcd = __gcd(x, y);
x /= gcd; y /= gcd;
ansx[id] = x; ansy[id] = y;
}

int main() {
n = read(); m = read();
bl = sqrt(n);
for (ll i = 1; i <= n; i++) {
c[i] = read();
}
for (ll i = 1; i <= m; i++) {
q[i].l = read(); q[i].r = read();
q[i].id = i;
}
sort(q+1, q+m+1, cmp); nl = q[1].l, nr = q[1].r;
for (ll i = q[1].l; i <= q[1].r; i++) {
add(c[i]);
}
getans(ans, (nr-nl+1)*(nr-nl)/2, q[1].id);
for (ll i = 2; i <= m; i++) {
update(q[i].l, q[i].r);
getans(ans, (nr-nl+1)*(nr-nl)/2, q[i].id);
}
for (ll i = 1; i <= m; i++) {
printf("%lld/%lld\n", ansx[i], ansy[i]);
}
return 0;
}

 评论