BZOJ2038：[2009国家集训队]小Z的袜子

浅谈莫队：https://www.cnblogs.com/AKMer/p/10374756.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=2038

首先答案肯定是\(\frac{\sum cnt_i*(cnt_i-1)}{r-l+1}\)，\(cnt_i\)表示第\(i\)种颜色的袜子的个数。

所以我们每次移动左右端点的时候，把当前添加或者删去的袜子的颜色的袜子对应的\(cnt_i*(cnt_i-1)\)从答案里面挖掉，然后让\(cnt_i\)加上或者减一，然后再把\(cnt_i*(cnt_i-1)\)加进答案里面去就行了。

时间复杂度：\(O(n\sqrt{n})\)

空间复杂度：\(O(n)\)

代码如下：

#include <cmath>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn=5e4+5;

ll ans;

int n,m,block;

int a[maxn],cnt[maxn],bel[maxn];

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

struct query {

    ll res;

    int l,r,id;

    bool operator<(const query &a)const {

        if(bel[l]!=bel[a.l])return bel[l]<bel[a.l];

        if(bel[l]&1)return r<a.r;return r>a.r;

    }

}q[maxn];

void change(int col,int v) {

    if(cnt[col])ans-=1ll*cnt[col]*(cnt[col]-1);

    cnt[col]+=v;

    if(cnt[col])ans+=1ll*cnt[col]*(cnt[col]-1);

}

bool cmp(query a,query b) {

    return a.id<b.id;

}

ll gcd(ll a,ll b) {

    if(!b)return a;

    return gcd(b,a%b);

}

int main() {

    n=read(),m=read(),block=sqrt(n);

    for(int i=1;i<=n;i++)

        a[i]=read(),bel[i]=(i-1)/block+1;

    for(int i=1;i<=m;i++)

        q[i].l=read(),q[i].r=read(),q[i].id=i;

    sort(q+1,q+m+1);

    int nowl=1,nowr=0;

    for(int i=1;i<=m;i++) {

        while(nowl<q[i].l)change(a[nowl++],-1);

        while(nowl>q[i].l)change(a[--nowl],1);

        while(nowr<q[i].r)change(a[++nowr],1);

        while(nowr>q[i].r)change(a[nowr--],-1);

        q[i].res=ans;

    }

    sort(q+1,q+m+1,cmp);

    for(int i=1;i<=m;i++) {

        if(q[i].l==q[i].r) puts("0/1");

        else {

            ll a=q[i].res,b=1ll*(q[i].r-q[i].l+1)*(q[i].r-q[i].l);

            ll g=gcd(a,b);a/=g,b/=g;

            printf("%lld/%lld\n",a,b);

        }

    }

    return 0;

}