[bzoj] 2038 小Z的袜子(hose) || 莫队

时间:2023-03-09 17:14:13
[bzoj] 2038 小Z的袜子(hose) || 莫队

原题

给出一个序列,求给定[l,r]内有任意取两个数,有多大概率是一样的


简单的莫队,每次+-当前区间里有的这个颜色的袜子的个数,最后除以(r-l+1)*(r-l)/2即可。

记得约分。

#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 50010
typedef long long ll;
using namespace std;
struct hhh
{
int x,y,l,id;
bool operator < (const hhh &b) const
{
if (b.l==l) return y<b.y;
return l<b.l;
}
}q[N];
ll n,m,s,l,r,a[N],ans1[N],ans2[N],cur,cnt[N]; ll read()
{
ll ans=0,fu=1;
char j=getchar();
for (;j<'0' || j>'9';j=getchar()) if (j=='-') fu=-1;
for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';
return ans*fu;
} ll gcd(ll x,ll y)
{
return y?gcd(y,x%y):x;
} int main()
{
n=read();s=sqrt(n);cnt[0]=1;
m=read();
for (int i=1;i<=n;i++) a[i]=read();
for (int i=1;i<=m;i++)
{
q[i].x=read();
q[i].y=read();
q[i].id=i;
q[i].l=(q[i].x-1)/s+1;
}
sort(q+1,q+m+1);
for (int i=1;i<=m;i++)
{
while (l<q[i].x) cur-=--cnt[a[l++]];
while (l>q[i].x) cur+=cnt[a[--l]]++;
while (r<q[i].y) cur+=cnt[a[++r]]++;
while (r>q[i].y) cur-=--cnt[a[r--]];
ans1[q[i].id]=cur;
ans2[q[i].id]=1LL*(r-l+1)*(r-l)/2;
}
for (int i=1;i<=m;i++)
{
ll g=gcd(ans1[i],ans2[i]);
printf("%lld/%lld\n",ans1[i]/g,ans2[i]/g);
}
return 0;
}