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

Iang_ · 2019-08-15 08:18:28 · 题解

莫队！！

这道题可以用绝妙的莫队（优美的暴力）解决QAQ
s[i]表示区间内第i种颜色的数量
很容易推出这一种袜子的贡献为
（s[i]*(s[i]-1)/2）,最后再累加答案就好了。
话不多说，下面附上AC代码：

#include<bits/stdc++.h>
using namespace std;
struct line
{
    int l,r,num;
} q[50010];
int n,m,k,a[50010],ans[50010],l=1,r,sum,s[50010],size,id[50010];
//这位置的颜色，第i个询问的答案，当前的左右端点，当前的总贡献，一个块的长度，这个位置是在第几块 
long long l1[50010],r1[50010];
bool cmp(line x,line y)
{
    if(id[x.r]==id[y.r])return x.l<y.l;
    else return x.r<y.r;
}
int main()
{
    scanf("%d%d",&n,&m);
    size=n/sqrt(m*2/3);//网上大佬说这样快（我也不知道为什么QAQ） 
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]),id[i]=(i-1)/size+1;
    for(int i=1; i<=m; i++)
        scanf("%d%d",&q[i].l,&q[i].r),q[i].num=i,l1[i]=q[i].l,r1[i]=q[i].r;
    sort(q+1,q+m+1,cmp);
    for(int i=1; i<=m; i++)
    {
        while(l<q[i].l)sum-=s[a[l]]*(s[a[l]]-1)/2,s[a[l]]--,sum+=s[a[l]]*(s[a[l]]-1)/2,l++;
        while(l>q[i].l)l--,sum-=s[a[l]]*(s[a[l]]-1)/2,s[a[l]]++,sum+=s[a[l]]*(s[a[l]]-1)/2;
        while(r<q[i].r)r++,sum-=s[a[r]]*(s[a[r]]-1)/2,s[a[r]]++,sum+=s[a[r]]*(s[a[r]]-1)/2;
        while(r>q[i].r)sum-=s[a[r]]*(s[a[r]]-1)/2,s[a[r]]--,sum+=s[a[r]]*(s[a[r]]-1)/2,r--;
        ans[q[i].num]=sum;
    }
    for(int i=1,x; i<=m; i++)
    {
        x=__gcd((long long)ans[i],(long long)(r1[i]-l1[i]+1)*(r1[i]-l1[i])/2);
        //约分成最简分数 
        if(l1[i]==r1[i])printf("0/1\n");
        else printf("%d/%lld\n",ans[i]/x,(long long)((r1[i]-l1[i]+1)*(r1[i]-l1[i])/2)/x);
    }
    return 0;//完美地结束！！ 
}