题目描述
作为一个生活散漫的人, 小 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 必须为最简分数.(详见样例)
样例输入
- 6 4
- 1 2 3 3 3 2
- 2 6
- 1 3
- 3 5
- 1 6
样例输出
- 2/5
- 0/1
- 1/1
- 4/15
[样例解释]
询问 1: 共 C(5,2)=10 种可能, 其中抽出两个 2 有 1 种可能, 抽出两个 3 有 3 种可能, 概率为(1+3)/10=4/10=2/5.
询问 2: 共 C(3,2)=3 种可能, 无法抽到颜色相同的袜子, 概率为 0/3=0/1.
询问 3: 共 C(3,2)=3 种可能, 均为抽出两个 3, 概率为 3/3=1/1.
注: 上述 C(a, b)表示组合数, 组合数 C(a, b)等价于在 a 个不同的物品中选取 b 个的选取方案数.
[数据规模和约定]
30% 的数据中 N,M ≤ 5000;
60% 的数据中 N,M ≤ 25000;
100% 的数据中 N,M ≤ 50000,1 ≤ L <R ≤ N,Ci ≤ N.
莫队模板题, 我们对于询问只记录分子部分的答案, 然后考虑当一个颜色的袜子数 $+1/-1$ 时对答案的影响. 当 $+1$ 时这种颜色的匹配数从 $\frac{x*(x-1)}{2}$ 变成了 $\frac{x*(x+1)}{2}$, 对答案的贡献增加了 $x$; 同理, 当 $-1$ 时这种颜色的匹配数从 $\frac{x*(x-1)}{2}$ 变成了 $\frac{(x-1)*(x-2)}{2}$, 对答案的贡献减少了 $x-1$. 所以只要在移动两个指针时对应加减分别增加或减少对答案的贡献即可, 而对于每个询问的分母则是询问区间长 *(询问区间长 - 1)/2. 求一下 $gcd$ 并将 $gcd$ 部分除掉即可. 注意当两个指针重合时要特判, 否则求出的 $gcd$ 为 $0$, 然后答案会除 $0$ 导致 $RE$.
- #include<set>
- #include<map>
- #include<queue>
- #include<cmath>
- #include<stack>
- #include<cstdio>
- #include<vector>
- #include<bitset>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #define ll long long
- using namespace std;
- ll ans;
- struct miku
- {
- int l,r,id;
- ll up,down;
- }a[50010];
- int n,m;
- int cnt[50010];
- int ql,qr;
- int block[50010];
- int c[50010];
- ll gcd(int x,int y)
- {
- return y==0?x:gcd(y,x%y);
- }
- void updata(int x,int num)
- {
- if(num==1)
- {
- ans+=1ll*cnt[x];
- cnt[x]++;
- }
- else
- {
- ans-=1ll*(cnt[x]-1);
- cnt[x]--;
- }
- }
- bool cmp(miku a,miku b)
- {
- return block[a.l]==block[b.l]?a.r<b.r:a.l<b.l;
- }
- bool cmp2(miku a,miku b)
- {
- return a.id<b.id;
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- int sum=sqrt(n);
- for(int i=1;i<=n;i++)
- {
- scanf("%d",&c[i]);
- block[i]=i/sum+1;
- }
- for(int i=1;i<=m;i++)
- {
- scanf("%d%d",&a[i].l,&a[i].r);
- a[i].id=i;
- }
- sort(a+1,a+1+m,cmp);
- ql=1,qr=0;
- for(int i=1;i<=m;i++)
- {
- while(ql<a[i].l)
- {
- updata(c[ql],-1);
- ql++;
- }
- while(ql>a[i].l)
- {
- updata(c[ql-1],1);
- ql--;
- }
- while(qr<a[i].r)
- {
- updata(c[qr+1],1);
- qr++;
- }
- while(qr>a[i].r)
- {
- updata(c[qr],-1);
- qr--;
- }
- if(ql==qr)
- {
- a[i].up=0,a[i].down=1;
- continue;
- }
- int len=qr-ql+1;
- ll d=gcd(ans,1ll*len*(len-1)/2);
- a[i].up=ans/d;
- a[i].down=(1ll*len*(len-1)/2)/d;
- }
- sort(a+1,a+1+m,cmp2);
- for(int i=1;i<=m;i++)
- {
- printf("%lld/%lld\n",a[i].up,a[i].down);
- }
- }
BZOJ2038[2009 国家集训队]小 Z 的袜子(hose)-- 莫队
来源: http://www.bubuko.com/infodetail-2949063.html