莫队---小z的袜子

总觉得莫队算法是个很玄学的东东

就像是这个题，刚开始没有看题解，T了好几把，后来发现分块这种神奇的操作，后来，，，手贱用map，结果又T了。

改了以后特意试了一下，不用分块比用分块慢了十倍多

最后统计的时候注意排列组合的运用就🆗啦

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

struct node
{
    int x,y,num;
    long long ans1,ans2;
}t[50100];

int n,m,l,r,qu;
int a[50100],ku[60000];
long long sum;
int q[50100];   

bool cmp(node k,node l)
{
    if(ku[k.x] == ku[l.x]) return k.y < l.y;  //分块
    else return k.x < l.x;
}

bool cmp1(node k,node l)
{
    return k.num < l.num;
}

long long gcd(long long x,long long y)
{
    if(y == 0) return x;
    return gcd(y, x % y);
}

int main()
{
    scanf("%d%d",&n,&m);
    qu = sqrt(n);
    for(int i = 1;i <= n; ++i)
        ku[i] = i / qu;
    for(int i = 1;i <= n; ++i)
    {
        scanf("%d",&a[i]);
    }
    for(int i = 0;i < m; ++i)
    {
        scanf("%d%d",&t[i].x,&t[i].y);
        t[i].num = i;
    }
    sort(t,t + m,cmp);
    l = 1; r = 0;
    sum = 0;
    for(int i = 0;i < m; ++i)
    {
        while(l < t[i].x)
        {
            sum -= q[a[l]] * (q[a[l]] - 1);
            q[a[l]]--;
            sum += q[a[l]] * (q[a[l]] - 1);
            l++;
        }
        while(l > t[i].x)
        {
            l--;
            sum -= q[a[l]] * (q[a[l]] - 1);
            q[a[l]]++;
            sum += q[a[l]] * (q[a[l]] - 1);
        }
        while(r > t[i].y)
        {
            sum -= q[a[r]] * (q[a[r]] - 1);
            q[a[r]]--;
            sum += q[a[r]] * (q[a[r]] - 1);
            r--;
        }
        while(r < t[i].y)
        {
            r++;
            sum -= q[a[r]] * (q[a[r]] - 1);
            q[a[r]]++;
            sum += q[a[r]] * (q[a[r]] - 1);
        }
        if(sum == 0 || l == r)
        {
            t[i].ans1 = 0;
            t[i].ans2 = 1;
        }
        else
        {
            long long W = 1LL* (r - l + 1) * (r - l);  //记得开long long 不然会乘爆
            long long x = gcd(sum,W);
            t[i].ans1 = sum / x;
            t[i].ans2 = W / x;
        }
    }
    sort(t,t + m,cmp1);
    for(int i = 0;i < m; ++i)
        printf("%lld/%lld\n",t[i].ans1,t[i].ans2);
    return 0;
}