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

时间：2023-03-09 03:11:59
洛谷P1494小Z的袜子 [国家集训队] 莫队

正解:莫队

解题报告:

这是,传送门qwq

昂大概是莫队板子题?

首先可以推出来答案是(∑C(2,color[i]))/C(2,r-l+1)趴?挺显然的不解释了qwq

然后显然除数直接做就成,考虑怎么求被除数 ∑C(2,color[i])

可以发现从[l,r]到[l,r+1]只++color[r+1]然后就没有改变了呢,那答案就只用改变一点儿(懒得港多少了太容易算了...),所以考虑用莫队

似,似乎就没了?

好趴果然板子题没什么好讲的呢

(啊想起来,就是,这个代码我觉得不是最板子的?就是和书上的表述不太一样,但是我感觉书上的可能跑得快些...?哪天写个书上版本的补上来qwq

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define rp(i,x,y) for(register ll i=x;i<=y;++i)

const ll N=+;

ll n,m,c[N],len,cjkl,cjkr,cjkans,num[N];

struct qest{ll l,r,id,bl;}q[N];

struct an{ll bcs,cs;}ans[N];

inline ll read()

{

    char ch=getchar();ll x=;bool y=;

    while(ch!='-' && (ch<'' || ch>''))ch=getchar();

    if(ch=='-')ch=getchar(),y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();

    return y?x:-x;

}

inline bool cmp(qest gold,qest genius)

{

    if(gold.bl==genius.bl)return gold.r<genius.r;

    return gold.bl<genius.bl;

}

inline ll update(ll col,ll data){cjkans-=num[col]*(num[col]-)/;num[col]+=data;cjkans+=num[col]*(num[col]-)/;}

int main()

{

    n=read();m=read();len=sqrt(n);

    rp(i,,n)c[i]=read();

    rp(i,,m)q[i].l=read(),q[i].r=read(),q[i].id=i,q[i].bl=(q[i].l-)/len+;

    sort(q+,q++m,cmp);cjkl=cjkr=q[].l;num[c[q[].l]]=;

    rp(i,,m)

    {

        while(cjkl<q[i].l)update(c[cjkl],-),++cjkl;

        while(cjkl>q[i].l)update(c[cjkl-],),--cjkl;

        while(cjkr<q[i].r)update(c[cjkr+],),++cjkr;

        while(cjkr>q[i].r)update(c[cjkr],-),--cjkr;

        if(q[i].l==q[i].r)ans[q[i].id].bcs=,ans[q[i].id].cs=;

        else{ans[q[i].id].bcs=cjkans,ans[q[i].id].cs=(q[i].r-q[i].l+)*(q[i].r-q[i].l)/;}

    }

    rp(i,,m)

    {

        ll t=__gcd(ans[i].bcs,ans[i].cs);if(t>)ans[i].bcs/=t,ans[i].cs/=t;

        printf("%lld/%lld\n",ans[i].bcs,ans[i].cs);

    }

    return ;

}

//maye改死我了QAQ

然后感觉没什么好讲的板子题就这么让我改了一个多小时:D

相关文章