测评结果 TLE求调

#include<bits/stdc++.h>
using namespace std;
const int MAXN=50006;
int a[MAXN];
long long sum[MAXN];
int pos[MAXN];
int n,m;
struct Q
{
    int l,r,k;
}q[MAXN];

struct A
{
    long long fz,fm;
}ans[MAXN];

bool cmp(Q a,Q b)
{
    if(pos[a.l]==pos[b.l])
    {
        if(pos[a.l]&1==1)return a.r<b.r;
        else return a.r>b.r;
    }
    else return pos[a.l]<pos[b.l];
}

void ad(int x)
{
    sum[a[x]]++;
}

void op(int x)
{
    sum[a[x]]--;
}

long long gcd(long long a,long long b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}

long long c(long long a,long long b)
{
    long long Ans=1;
    for(int i=a;i>a-b;i--)Ans*=i;
    for(int i=1;i<=b;i++)Ans/=i;
    return Ans;
}

int main()
{
    cin>>n>>m;
    int Max=0;
    int t=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        Max=max(Max,a[i]);
        pos[i]=(i-1)/t+1;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>q[i].l>>q[i].r;
        q[i].k=i;
    }   

    sort(q+1,q+1+m,cmp);
    int l=1;
    int r=0;
    for(int i=1;i<=m;i++)
    {
        while(q[i].l>l)op(l++);
        while(q[i].l<l)ad(--l);
        while(q[i].r>r)ad(++r);
        while(q[i].r<r)op(r--);
        long long Z=0;
        long long M=0;
        M=c(q[i].r-q[i].l+1,2);
        for(int i=1;i<=Max;i++)
        {
            if(sum[i]>=2)
            {
                Z+=c(sum[i],2);
            }
        }
        if(Z==0)
        {
            ans[q[i].k].fz=0;
            ans[q[i].k].fm=1;
        }
        else
        {
            long long p=gcd(M,Z);
            M/=p;
            Z/=p;
            ans[q[i].k].fm=M;
            ans[q[i].k].fz=Z;
        }
    }
    for(int i=1;i<=m;i++)
    {
        cout<<ans[i].fz<<'/'<<ans[i].fm<<endl;
    }
    return 0;
}