[BZOJ 2038] 小z的袜子

link

设颜色为$i$的个数为$a_i$

我们可以发现$[l,r]$里面的答案为

$frac{ sum _{i=1}^x a_i imes (a_i-1)}{sum_{i=1}^x a_i}$

化简得

$frac{sum_{i=1}^x a_i^2-(r-l+1)}{(r-l+1) imes(r-l)}$

所以只要维护平方就行，用分块进行莫队，然后暴力维护平方，时间复杂度:$O(n imes sqrt(n))$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define int long long
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=50001;
struct node{
    int l,r,id,posl,posr;
    int fz,fm;
}x[MAXN];
int ans,n,col[MAXN],q,blo,bl[MAXN];
bool cmp1(node x1,node x2){
    if(x1.posl==x2.posl) return x1.r<x2.r;
    return x1.l<x2.l;
}
bool cmp2(node x1,node x2){
    return x1.id<x2.id;
}
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int s[MAXN];
void update(int color,int dig){
    ans-=s[color]*s[color];
    s[color]+=dig;
    ans+=s[color]*s[color];
}
void solve(){
    int l=1,r=0;
    for(int i=1;i<=q;i++){
        int size=(x[i].r-x[i].l+1);
        int fm=size*(size-1);
        for(;r<x[i].r;r++) update(col[r+1],1);
        for(;r>x[i].r;r--) update(col[r],-1);
        for(;l<x[i].l;l++) update(col[l],-1);
        for(;l>x[i].l;l--) update(col[l-1],1);
        if(x[i].l==x[i].r){
            x[i].fm=1,x[i].fz=0;
            continue;
        }
        int fz=ans-size;
        int st_gcd=gcd(fm,fz);
        fm/=st_gcd,fz/=st_gcd;
        x[i].fz=fz,x[i].fm=fm;
    }
}
signed main(){
//    freopen("1.in","r",stdin);
    n=read(),q=read();blo=sqrt(n);
    for(int i=1;i<=n;i++) col[i]=read();
    for(int i=1;i<=n;i++) bl[i]=(i-1)/blo+1;
    for(int i=1;i<=q;i++) x[i].id=i,x[i].l=read(),x[i].r=read(),x[i].posl=bl[x[i].l],x[i].posr=bl[x[i].r];
    sort(x+1,x+q+1,cmp1);
    solve();
    sort(x+1,x+q+1,cmp2);
    for(int i=1;i<=q;i++) printf("%d/%d
",x[i].fz,x[i].fm);
}