题目地址：洛谷：【P1494】[国家集训队]小Z的袜子 – 洛谷、BZOJ：Problem 2038. — [2009国家集训队]小Z的袜子(hose)

题目描述

作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。
然而数据中有L=R的情况，请特判这种情况，输出0/1。

题意简述

有一个颜色序列，每次询问给出一个区间，求从区间中任选两个位置颜色相同的概率，要求输出最简分数。

输入输出格式

输入格式：
输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。接下来一行包含N个正整数Ci，其中Ci表示第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 ≤ 5000；
60%的数据中 N,M ≤ 25000；
100%的数据中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。

题解

参考资料：【莫队算法】 – 大米饼 – 博客园
第一次写莫队。
我们考虑离线解决这个问题。发现对于每个询问的答案，我们可以用O(1)时间在[l, r]区间和[l±1, r]或[l, r±1]这些区间之间转移。此时，我们考虑将询问分块，按照左端点的块号与右端点双关键字排序。这样，我们可以获得在相邻询问之间转移答案的最高效率，实现O(n \sqrt{n})的复杂度。
具体而言，对于本题，分母显然就是len(len-1)，而分子是每种颜色的数量平方和-len。我们维护一下区间每种颜色的数量及其平方和，某颜色数量更改时顺便更新平方和即可。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cmath>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 50005;

inline LL gcd(LL a, LL b) {
    if(!b) return a;
    return gcd(b, a % b);
}

int n, m, block, col[MAXN], ccnt[MAXN];
LL ans1[MAXN], ans2[MAXN], now;

inline int bid(int pos) {
    return pos / block + 1;
}

inline void apply(int pos, int add) {
    now -= 1ll * ccnt[col[pos]] * ccnt[col[pos]];
    ccnt[col[pos]] += add;
    now += 1ll * ccnt[col[pos]] * ccnt[col[pos]];
}

struct Query {
    int l, r, id;
} qur[MAXN];

inline bool cmp(Query a, Query b) {
    return bid(a.l) == bid(b.l) ? a.r < b.r : a.l < b.l;
}

int main() {
    n = readint(); m = readint(); block = sqrt(n);
    for(int i = 1; i <= n; i++) {
        col[i] = readint();
    }
    for(int i = 1; i <= m; i++) {
        qur[i].l = readint(); qur[i].r = readint(); qur[i].id = i;
    }
    std::sort(qur + 1, qur + m + 1, cmp);
    int l = 1, r = 0;
    for(int i = 1; i <= m; i++) {
        for(; l < qur[i].l; l++) apply(l, -1);
        for(; l > qur[i].l; l--) apply(l - 1, 1);
        for(; r < qur[i].r; r++) apply(r + 1, 1);
        for(; r > qur[i].r; r--) apply(r, -1);
        if(qur[i].l == qur[i].r) {
            ans1[qur[i].id] = 0; ans2[qur[i].id] = 1; continue;
        }
        ans1[qur[i].id] = now - (qur[i].r - qur[i].l + 1);
        ans2[qur[i].id] = 1ll * (qur[i].r - qur[i].l + 1) * (qur[i].r - qur[i].l);
        LL g = gcd(ans1[qur[i].id], ans2[qur[i].id]); 
        ans1[qur[i].id] /= g; ans2[qur[i].id] /= g;
    }
    for(int i = 1; i <= m; i++) {
        printf("%lld/%lld\n", ans1[i], ans2[i]);
    }
    return 0;
}