Loading...

洛谷P1494 [国家集训队]小Z的袜子

check评论:0 条 remove_red_eye浏览量:546 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-26

一道莫队裸题

我们可以知道,查询区间$[l,r]$的答案,就相当于查询$\frac{\sum_{\text{出现过}i} C_{A_i}^2}{C_{r-l+1}^2}$

其中$A_i$表示$i$的出现次数,我们规定$C_1^2=0$

然后每次查询的分母就可以直接算出,分子我们每次减去原来的个数,加上新个数即可,关于组合数,我们提前预处理以加快速度

#include <bits/stdc++.h>
using namespace std;
int ans1[50010],ans2[50010],n,m,block,a[50010],tong[50010],c[50010];
struct query
{
    int l,r,id;
}q[50010];
bool cmp(query a,query b)
{
    return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r;
}
void pre()
{
    c[2]=1;
    for(int i=3;i<=n;i++)
    {
        c[i]=c[i-1]+(i-1);
    }
}
int gcd(int a,int b)
{
    if(a<b)
    {
        swap(a,b);
    }
    if(b==0)
    {
        return a;
    }    
    return gcd(a%b,b);
}
int main()
{
    cin>>n>>m;
    block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    pre();
    sort(q+1,q+m+1,cmp);
    int l=0,r=0,nowans1=0,nowans2=0;
    for(int i=1;i<=m;i++)
    {
        if(q[i].l==q[i].r)
        {
            ans1[q[i].id]=0;
            ans2[q[i].id]=1;
            continue;
        }
        nowans2=c[q[i].r-q[i].l+1];
        while(l<q[i].l)
        {
            nowans1-=c[tong[a[l]]];
            tong[a[l]]--;
            nowans1+=c[tong[a[l]]];
            l++;
        }
        while(l>q[i].l)
        {
            l--;
            nowans1-=c[tong[a[l]]];
            tong[a[l]]++;
            nowans1+=c[tong[a[l]]];
        }
        while(r<q[i].r)
        {
            r++;
            nowans1-=c[tong[a[r]]];
            tong[a[r]]++;
            nowans1+=c[tong[a[r]]];
        }
        while(r>q[i].r)
        {
            nowans1-=c[tong[a[r]]];
            tong[a[r]]--;
            nowans1+=c[tong[a[r]]];
            r--;
        }
        int k=gcd(nowans1,nowans2);
        ans1[q[i].id]=nowans1/k;
        ans2[q[i].id]=nowans2/k;
    }
    for(int i=1;i<=m;i++)
    {
        printf("%d/%d\n",ans1[i],ans2[i]);
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名