作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……
具体来说,小Z把这N只袜子从1到N编号,然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z,他有多大的概率抽到两只颜色相同的袜子。当然,小Z希望这个概率尽量高,所以他可能会询问多个(L,R)以方便自己选择。
作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……
具体来说,小Z把这N只袜子从1到N编号,然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z,他有多大的概率抽到两只颜色相同的袜子。当然,小Z希望这个概率尽量高,所以他可能会询问多个(L,R)以方便自己选择。
输入文件第一行包含两个正整数N和M。N为袜子的数量,M为小Z所提的询问的数量。接下来一行包含N个正整数Ci,其中Ci表示第i只袜子的颜色,相同的颜色用相同的数字表示。再接下来M行,每行两个正整数L,R表示一个询问。
包含M行,对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1,否则输出的A/B必须为最简分数。(详见样例)
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn=50005; 5 typedef long long ll; 6 7 inline int read() 8 { 9 int i=0;char c=getchar(); 10 while(c>'9'||c<'0')c=getchar(); 11 while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar(); 12 return i; 13 } 14 15 struct node{ 16 int l,r,pos; 17 }a[maxn]; 18 struct Node{ 19 ll x,y; 20 }ans[maxn]; 21 int b[maxn],sum[maxn],belong[maxn]; 22 int n,m,now,l,r,block; 23 24 inline bool cmp(node x,node y) 25 { 26 return belong[x.l]==belong[y.l]?x.r<y.r:belong[x.l]<belong[y.l]; 27 } 28 29 inline ll gcd(ll x,ll y) 30 { 31 return x==0?y:gcd(y%x,x); 32 } 33 34 int main() 35 { 36 n=read(); 37 m=read(); 38 block=sqrt(n); 39 for(int i=1;i<=n;i++) 40 { 41 b[i]=read(); 42 belong[i]=(i-1)/block+1; 43 } 44 for(int i=1;i<=m;i++) 45 a[i]=(node){read(),read(),i}; 46 sort(a+1,a+1+m,cmp); 47 l=r=a[1].l; 48 sum[b[a[1].l]]=1; 49 for(int i=1;i<=m;i++) 50 { 51 while(l<a[i].l)now-=(--sum[b[l++]]); 52 while(r>a[i].r)now-=(--sum[b[r--]]); 53 while(l>a[i].l)now+=(sum[b[--l]]++); 54 while(r<a[i].r)now+=(sum[b[++r]]++); 55 ans[a[i].pos]=(Node){now,(ll)(r-l+1)*(r-l)/2}; 56 } 57 for(int i=1;i<=m;i++) 58 { 59 if(ans[i].x==0||ans[i].y==0) 60 cout<<"0/1"<<endl; 61 else 62 { 63 ll c=gcd(ans[i].x,ans[i].y); 64 printf("%lld/%lld\n",ans[i].x/c,ans[i].y/c); 65 } 66 } 67 return 0; 68 }
如对本文有疑问, 点击进行留言回复!!
网友评论