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

1. 题目

题目描述

作为一个生活散漫的人，小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小 Z 再也无法忍受这恼人的找袜子过程，于是他决定听天由命……

具体来说，小 Z 把这 $N$ 只袜子从 $1$ 到 $N$ 编号，然后从编号 $L$ 到 $R$ (尽管小 Z 并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬）。

你的任务便是告诉小 Z，他有多大的概率抽到两只颜色相同的袜子。当然，小 Z 希望这个概率尽量高，所以他可能会询问多个 $(L,R)$ 以方便自己选择。

然而数据中有 $L=R$ 的情况，请特判这种情况，输出 $0/1$ 。

输入格式

输入文件第一行包含两个正整数 $N$ 和 $M$ 。 $N$ 为袜子的数量， $M$ 为小 Z 所提的询问的数量。接下来一行包含 $N$ 个正整数 $C_i$ ，其中 $C_i$ ，表示第 $i$ 只袜子的颜色，相同的颜色用相同的数字表示。再接下来 $M$ 行，每行两个正整数 $L,R$ 表示一个询问。

输出格式

包含 $M$ 行，对于每个询问在一行中输出分数 $A/B$ 表示从该询问的区间 $[L,R]$ 中随机抽出两只袜子颜色相同的概率。若该概率为 $0$ 则输出 $0/1$ ，否则输出的 $A/B$ 必须为最简分数。（详见样例）

输入输出样例

输入 #1

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

输出 #1

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

说明/提示

$30\%$ 的数据中， $N,M \leq 5000$ ；

$60\%$ 的数据中， $N,M \leq 25000$ ；

$100\%$ 的数据中， $N,M \leq 50000$ ， $1 \leq L < R \leq N$ ， $C_i \leq N$ 。

2. 题解

分析

一看题目，可以离线查询，而且 $O(m \sqrt{n})$ 的时间复杂度可以过，那么可以考虑用莫队算法。

假设袜子总数为 $n$ ， $color[i]$ 表示第 $i$ 个位置的袜子颜色。

考虑由区间 $[l,r]$ 转移到区间 $[l,r+1]$ （其它三个相邻区间分析类似），设 $[l,r]$ 中颜色相同的两只袜子的配对数为 $ans_{l,r}$ ， $count[j]$ 表示区间 $[l,r]$ 中颜色为 $j$ 的袜子数目，则由排列组合可知

$\begin{array}{rl} x &= count[color[r+1]] \\ y &= count[color[r+1]]+1 \\ ans_{l,r+1} &= ans_{l,r} + (C_{y}^2 - C_{x}^2) \\ &= ans_{l,r} + count[color[r+1]] \end{array}$

因此，由区间 $[l,r]$ 转移到其相邻的区间的时间复杂度为 $O(1)$ ，故可以使用莫队算法。

已知区间 $[l,r]$ 中颜色相同的两只袜子的配对数为 $ans_{l,r}$ ，则答案为 $ans_{l,r} / C_{r-l+1}^2$ 。由于要求最简分数，因此可以使用辗转相除法计算分子和分母的最大公因数 $d = gcd(ans_{l,r}, C_{r-l+1}^2)$ ，最终答案为 $\frac{ans_{l,r}}{d} / \frac{C_{r-l+1}^2}{d}$ 。

代码

#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;
}