题解 P1494 【[国家集训队]小Z的袜子】

· · 题解

题目分析

首先我们看一个简化的问题

给定一个序列，以及多组询问，针对每组询问，回答该区间有多少方案选出两个值相同的元素（不能调换左右）。

在上面的问题中，假设有n个值相同的元素，那方案数肯定是n*(n-1)/2,所以每个元素对答案贡献为在它之前的元素个数；

那我们回到之前的问题

题目中说可以调换左右，但因为所有的的袜子可以调换左右，所以就等价与上面的问题，我们只要把所有的选出的相同袜子的方案数除以所有的方案数。

附代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,t;
int a[500005];
struct node
{
    int l,r;
    int pos;
}e[500005];
inline bool cmp(node a,node b)
{
    return (a.r/t)==(b.r/t)?a.l<b.l:a.r<b.r;//排序; 
}
long long ans[500005],cnt[500005];//不开long long一场空; 
long long sum[500005];
long long k=0;
inline void sk(int x)
{
    k+=cnt[a[x]];
    cnt[a[x]]++;
}
inline void hk(int x)
{
    cnt[a[x]]--;
    if(cnt[a[x]]!=0) k-=cnt[a[x]];
}
int f[500005];
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;i++) scanf("%d",&a[i]);
    t=n/sqrt(m*2/3);
    for(register int i=1;i<=m;i++)
    {
        scanf("%d%d",&e[i].l,&e[i].r);
        e[i].pos=i;
    }
    sort(e+1,e+m+1,cmp);
    int l=1,r=0;
    for(register int i=1;i<=m;i++)
    {
        while(l<e[i].l) hk(l++); 
        while(l>e[i].l) sk(--l);
        while(r<e[i].r) sk(++r);
        while(r>e[i].r) hk(r--);
        long long d=e[i].r-e[i].l+1;
        if(e[i].l==e[i].r) f[e[i].pos]=1;
        ans[e[i].pos]=k;
        sum[e[i].pos]=d*(d-1)/2;
    }
    for(register int i=1;i<=m;i++)
    {
        long long d=__gcd(ans[i],sum[i]);
        if(f[i]==1) printf("0/1\n");//特判，就因为这个我交了好几发. 
        else printf("%lld/%lld\n",ans[i]/d,sum[i]/d);
    }
    return 0;
}