P1494「[国家集训队]小Z的袜子」

6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

2/5
0/1
1/1
4/15

#include <bits/stdc++.h>
#define ll int
#define MAXN 100000
using namespace std;

ll cnt[MAXN];

// 辗转相除法
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a%b);
}

ll bz;              // 分块大小

// 莫队
struct MO {
    // 查询区间
    struct Query {
        ll l, r;
        ll idx, ntr, dtr;
        bool operator < (Query q) const {
            return l/bz != q.l/bz ? l < q.l : 
                (l/bz) & 1 ? r < q.r : r > q.r;
        }
    };
    ll n, m;            // 数列长度，查询次数
    ll ans;             // 查询答案
    ll color[MAXN];     // 颜色数组
    ll result[MAXN][2]; // 答案数组
    Query query[MAXN];  // 查询区间数组
    // 初始化
    MO() {
        ans = 0;
        memset(query, 0, sizeof(query));
    }
    // 区间长度增一
    void add(ll col) {
        ++cnt[col];
        ans += cnt[col] - 1;
    }
    // 区间长度减一
    void del(ll col) {
        ans -= cnt[col] - 1;
        --cnt[col];
    }
    // 求解答案
    void solver() {
        sort(query, query+m);
        ll l = query[0].l;
        ll r = query[0].l-1;
        for(ll i = 0; i < m; ++i) {
            if(query[i].l >= query[i].r) {
                query[i].ntr = 0;
                query[i].dtr = 1;
                continue;
            }
            while(r < query[i].r) {
                add(color[++r]);
            }
            while(r > query[i].r) {
                del(color[r--]);
            }
            while(l < query[i].l) {
                del(color[l++]);
            }
            while(l > query[i].l) {
                add(color[--l]);
            }
            if(!ans) {
                query[i].ntr = 0;
                query[i].dtr = 1;
            } else {
                ll s = (r-l)%2 ? (r-l+1)/2*(r-l) : (r-l)/2*(r-l+1);
                ll d = gcd(ans, s);
                query[i].ntr = ans / d;
                query[i].dtr = s / d;
            }
        }
        for(ll i = 0; i < m; ++i) {
            result[query[i].idx][0] = query[i].ntr;
            result[query[i].idx][1] = query[i].dtr;
        }
        for(ll i = 0; i < m; ++i) {
            printf("%d/%d\n", result[i][0], result[i][1]);
        }
    }
};

int main()
{
    MO z;
    scanf("%d%d", &z.n, &z.m);
    bz = (int)sqrt(z.n);
    for(ll i = 0; i < z.n; ++i) {
        scanf("%d", &z.color[i]);
    }
    ll l, r;
    for(ll i = 0; i < z.m; ++i) {
        scanf("%d%d", &l, &r);
        z.query[i].l = l-1;
        z.query[i].r = r-1;
        z.query[i].idx = i;
    }
    z.solver();
    return 0;
}