洛谷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=50000+100;
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=0;bool y=1;
while(ch!='-' && (ch<'0' || ch>'9'))ch=getchar();
if(ch=='-')ch=getchar(),y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),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]-1)/2;num[col]+=data;cjkans+=num[col]*(num[col]-1)/2;}
int main()
{
n=read();m=read();len=sqrt(n);
rp(i,1,n)c[i]=read();
rp(i,1,m)q[i].l=read(),q[i].r=read(),q[i].id=i,q[i].bl=(q[i].l-1)/len+1;
sort(q+1,q+1+m,cmp);cjkl=cjkr=q[1].l;num[c[q[1].l]]=1;
rp(i,1,m)
{
while(cjkl<q[i].l)update(c[cjkl],-1),++cjkl;
while(cjkl>q[i].l)update(c[cjkl-1],1),--cjkl;
while(cjkr<q[i].r)update(c[cjkr+1],1),++cjkr;
while(cjkr>q[i].r)update(c[cjkr],-1),--cjkr;
if(q[i].l==q[i].r)ans[q[i].id].bcs=0,ans[q[i].id].cs=1;
else{ans[q[i].id].bcs=cjkans,ans[q[i].id].cs=(q[i].r-q[i].l+1)*(q[i].r-q[i].l)/2;}
}
rp(i,1,m)
{
ll t=__gcd(ans[i].bcs,ans[i].cs);if(t>1)ans[i].bcs/=t,ans[i].cs/=t;
printf("%lld/%lld\n",ans[i].bcs,ans[i].cs);
}
return 0;
}
//maye改死我了QAQ