BZOJ2038 - [2009国家集训队]小Z的袜子(hose)

2017/10/22

题目

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

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

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

做法

按照静态莫队的要求根号分块,然后大力维护答案即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int SIZ = 50000 + 2007;
int N, M;
int c[SIZ], pos[SIZ];

struct qry {
    int l, r, id; LL a, b;
} Q[SIZ];

bool cmp(const qry &a, const qry &b) {
    if(pos[a.l] == pos[b.l]) return a.r < b.r;
    return a.l < b.l;
}

LL ans;
LL s[SIZ];
void update(int p, int add) {
    ans -= s[c[p]] * s[c[p]];
    s[c[p]] += add;
    ans += s[c[p]] * s[c[p]];
}

LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
void solve() {
    for(int i=1,l=1,r=0;i<=M;i++) {
        for(;r<Q[i].r;r++)
            update(r+1, 1);

        for(;r>Q[i].r;r--)
            update(r, -1);

        for(;l<Q[i].l;l++)
            update(l, -1);

        for(;l>Q[i].l;l--)
            update(l-1, 1);

        if(Q[i].l == Q[i].r) {
            Q[i].a = 0, Q[i].b = 1;
            continue;
        }

        Q[i].a = ans - (Q[i].r - Q[i].l + 1);
        Q[i].b = LL(Q[i].r - Q[i].l + 1) * (Q[i].r - Q[i].l);
        LL k = gcd(Q[i].a, Q[i].b);
        Q[i].a /= k, Q[i].b /= k;
    }
}

LL answ[SIZ][2];

int main() {
    scanf("%d %d", &N, &M);

    for(int i=1;i<=N;i++)
        scanf("%d", &c[i]);

    int blk = int(ceil(sqrt(float(N))));

    for(int i=1;i<=N;i++)
        pos[i] = (i-1) / blk + 1;

    for(int i=1;i<=M;i++) {
        scanf("%d %d", &Q[i].l, &Q[i].r);
        Q[i].id = i;
    }
    

    sort(Q+1, Q+M+1, cmp);
    solve();
    
    for(int i=1;i<=M;i++) answ[Q[i].id][0] = Q[i].a, answ[Q[i].id][1] = Q[i].b;
    for(int i=1;i<=M;i++) printf("%lld/%lld\n", answ[i][0], answ[i][1]);
}