记录编号	322675	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2010] 小Z的袜子	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.850 s
提交时间	2016-10-15 14:23:37	内存使用	2.15 MiB

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <string>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
typedef long long LL;
using namespace std;
int fast_read()
{
    int r;
    char c;
    while(c = getchar())    
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return r;
}
//小z袜子
#define MAXN 50002
int waz[MAXN];
int cnt[MAXN];
struct que
{
    int l, r;
    int bk;
    int id;
    LL ans;
    LL base;
    bool operator<(const que &o) const
    {
        return bk < o.bk || (bk == o.bk && r < o.r);
    }
}qs[MAXN];
int rank[MAXN];

LL gcd(LL a, LL b)
{
    if(b == 0)return a;
    else return gcd(b, a%b);
}
bool cmp(int x, int y)
{
    return qs[x] < qs[y];
}
LL C(int n, int k) //组合。mdzz用这个配合stl算就TLE了...
{
    LL ans = 1;
    for(int i = k+1; i <= n; i++)ans *= i;
    for(int i = 2; i <= n-k; i++)ans /= i;
    return ans;
}
int main()
{
    freopen("hose.in", "r", stdin);
    freopen("hose.out", "w", stdout);
    int n, m;
    n = fast_read();
    m = fast_read();
    int magic = (int)sqrt(n);
    for(int i = 1; i <= n; i++)
        waz[i] = fast_read();
    for(int i = 0; i < m; i++)
    {
        rank[i] = i;
        que &q = qs[i];
        q.ans = 0;
        q.l = fast_read();
        q.r = fast_read();
        q.bk = q.l/magic;
        q.id = i;
    }
    sort(rank, rank+m, cmp);
    int l = 2, r = 1;
    long long ans = 0;
    for(int i = 0; i < m; i++)
    {
        que &q = qs[rank[i]];
        while(l < q.l)
        {
            cnt[waz[l]]--;
            ans -= cnt[waz[l]];
            l++;
        }
        while(r > q.r)
        {
            cnt[waz[r]]--;
            ans -= cnt[waz[r]];
            r--;
        }
        while(l > q.l)
        {
            l--;
            ans += cnt[waz[l]];
            cnt[waz[l]]++;
        }
        while(r < q.r)
        {
            r++;
            ans += cnt[waz[r]];
            cnt[waz[r]]++;
        }
        q.ans = ans;
        q.base = (((LL)(r-l))*(LL)(r-l+1))/2;
        if(q.base)
        {
            long long k = gcd(q.ans, q.base);
            q.ans /= k;
            q.base /= k;
        }else
        {
            q.ans = 0;
            q.base = 1;
        }
    }
    for(int i = 0; i < m; i++)
    {
        que &q = qs[i];
        printf("%lld/%lld\n", q.ans, q.base);
    }
    return 0;
}