BZOJ2038 小Z的袜子

题意

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

题解

这题如果可以离线的话,是可以用莫队来做的。但是如果题目强制在线,该怎么办呢?这里讲一种使用分块的在线算法。
容易看出只要求颜色相同的方案数就可以了。接下来,先预处理出分出的$\sqrt{n}$个块中,每个块的末尾这个位置上每种颜色的前缀和。注意到每加入一个颜色,那么增加的贡献就是原来这个颜色的个数,然后就可以预处理出第$i$个块到第$j$个块之间的答案。接下来求解答案时,只需先将整块的答案加上,解决边角料时,只需加上当前这种颜色的个数即可。
时间复杂度$O(n\sqrt{n})$。
其实这也算是分块题的一个套路吧,大概就是先计算出第$i$个块到第$j$个块的答案。回答询问时,先基于整块的答案,再来处理边角料的贡献。

代码

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
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=5e4+10;
const int maxblock=250+10;
const int maxcol=1e2+10;
int a[maxn],beg[maxblock],end[maxblock],id[maxn];
int Sum[maxblock][maxn],ans[maxblock][maxblock],tmp[maxn];
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
int main(){
int i,j,k,m,n,q,type;
#ifndef ONLINE_JUDGE
freopen("BZOJ2038.in","r",stdin);
freopen("BZOJ2038.out","w",stdout);
#endif
n=read();q=read();
int blocksz=(int)(sqrt(n)+0.5);
int blockcnt=0;
for(i=1;i<=n;i++){
id[i]=(i-1)/blocksz+1;
if(i%blocksz==1)beg[++blockcnt]=i;
if(i%blocksz==0 || i==n)end[blockcnt]=i;
}
for(i=1;i<=blockcnt;i++){
memcpy(Sum[i],Sum[i-1],sizeof(Sum[i]));
for(j=beg[i];j<=end[i];j++)
Sum[i][a[j]=read()]++;
}
for(i=1;i<=blockcnt;i++){
for(j=i;j<=blockcnt;j++){
ans[i][j]=ans[i][j-1];
for(k=beg[j];k<=end[j];k++)
ans[i][j]+=tmp[a[k]],tmp[a[k]]++;
}
memset(tmp,0,sizeof(tmp));
}
int lans=0;
while(q--){
int l=read(),r=read();
if(l==r){
puts("0/1");
continue;
}
lans=0;
if(id[l]+1>=id[r]){
for(i=l;i<=r;i++)lans+=tmp[a[i]],tmp[a[i]]++;
for(i=l;i<=r;i++)tmp[a[i]]--;
int gcd=__gcd(1ll*lans,1ll*(r-l+1)*(r-l)/2);
printf("%d/%lld\n",lans/gcd,1ll*(r-l+1)*(r-l)/2/gcd);continue;
}
lans=ans[id[l]+1][id[r]-1];
for(i=l;i<=end[id[l]];i++)lans+=Sum[id[r]-1][a[i]]-Sum[id[l]][a[i]],Sum[id[r]-1][a[i]]++;
for(i=beg[id[r]];i<=r;i++)lans+=Sum[id[r]-1][a[i]]-Sum[id[l]][a[i]],Sum[id[r]-1][a[i]]++;
for(i=l;i<=end[id[l]];i++)Sum[id[r]-1][a[i]]--;
for(i=beg[id[r]];i<=r;i++)Sum[id[r]-1][a[i]]--;
int gcd=__gcd(1ll*lans,1ll*(r-l+1)*(r-l)/2);
printf("%d/%lld\n",lans/gcd,1ll*(r-l+1)*(r-l)/2/gcd);continue;
}
return 0;
}