题目：点击此处

思路：求出每个区间中从每种颜色中选两个  的种类数的和 

如果和为零输出0/1

否则输出  和/ ( (r-l+1)*(r-l)/2 )   最简形式

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn=1e6+5;
struct node
{
    ll l,r,i;
}pos[maxn];

ll n,block,q,l,r,ans=0;
ll mp[maxn],c[maxn],a[maxn];
struct an{
    ll zi,mu;
}answer[maxn];
bool cmp(node a,node b)
{
    if(a.l/block!=b.l/block)
        return a.l/block<b.l/block;
    return a.r<b.r;
}
void add(ll x)
{
    ans+=mp[a[x]];
    mp[a[x]]++;
}
void remov1e(ll x)
{
    mp[a[x]]--;
    ans-=mp[a[x]];
}
int main()
{
    scanf("%lld%lld",&n,&q);block=sqrt(1.0*n);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(ll i=1;i<=q;i++)
    {
        scanf("%lld%lld",&pos[i].l,&pos[i].r);
        pos[i].i=i;
    }
    sort(pos+1,pos+1+q,cmp);
    ll cl=pos[1].l,cr=cl-1;
    for(ll i=1;i<=q;i++)
    {

        l=pos[i].l,r=pos[i].r;

        while(cl<l)
        {
            remov1e(cl);
            cl++;
        }
        while(cl>l)
        {
            add(cl-1);
            cl--;
        }
        while(cr<r)
        {
            add(cr+1);
            cr++;
        }

        while(cr>r)
        {
            remov1e(cr);
            cr--;
        }
        ll zi=ans;
        if(zi==0)
        {
            answer[pos[i].i].zi=0;
            answer[pos[i].i].mu=1;
        }
        else {
            ll mu=(r-l+1)*(r-l)/2;
            ll g=__gcd(zi,mu);
            zi/=g;mu/=g;
            answer[pos[i].i].zi=zi;
            answer[pos[i].i].mu=mu;
        }

    }
    for(ll i=1;i<=q;i++)
        cout<<answer[i].zi<<"/"<<answer[i].mu<<endl;
    return 0;
}