BZOJ2038 小Z的袜子 <莫队>

Posted on Symbols count in article: 991 Reading time ≈ 4 mins.

Problem

小Z的袜子

Description

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

Input

输入文件第一行包含两个正整数NN和MM。NN为袜子的数量，MM为小ZZ所提的询问的数量。接下来一行包含NN个正整数CiC_i，其中CiC_i表示第ii只袜子的颜色，相同的颜色用相同的数字表示。再接下来MM行，每行两个正整数LL，RR表示一个询问。

Output

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

Sample Input

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

Sample Output

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

Hint

样例解释
询问11：共C52=10C_5^2=10种可能，其中抽出两个22有11种可能，抽出两个33有33种可能，概率为(1+3)/10=4/10=2/5(1+3)/10=4/10=2/5。
询问22：共C32=3C_3^2=3种可能，无法抽到颜色相同的袜子，概率为0/3=0/10/3=0/1。
询问33：共C32=3C_3^2=3种可能，均为抽出两个3，概率为3/3=1/13/3=1/1。
数据规模和约定
30%30\%的数据中 N,M≤5000N,M \le 5000；
60%60\%的数据中 N,M≤25000N,M \le 25000；
100%100\%的数据中 N,M≤50000N,M \le 50000，1≤L<R≤N1\le L < R \le N，Ci≤NC_i \le N。

标签：莫队

Solution

莫队经典例题。
不懂莫队的可以戳这里：http://www.cnblogs.com/hzf-sbit/p/4056874.html
简单来说，莫队就是将询问离线，维护双指针，暴力扩展或缩小范围，为了加速，用分块，可以达到O(nn)O(n\sqrt{n})。

Code

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define MAX_N 50000
using namespace std;
typedef long long ll;
int n, m;
int col[MAX_N+5], f[MAX_N+5], pos[MAX_N+5];
ll gcd(ll a, ll b)    {return (b == 0) ? a : gcd(b, a%b);}
struct Query {
    int id, l, r;	ll a, b;
    void reduction() {ll tmp = gcd(a, b);	a /= tmp, b /= tmp;}
} Q[MAX_N+5];
bool cmp_l(const Query &a, const Query &b) {return pos[a.l] < pos[b.l] || (pos[a.l] == pos[b.l] && a.r < b.r);}
bool cmp_id(const Query &a, const Query &b) {return a.id < b.id;}
void add(int c, ll &tmp, int x) {tmp += x*2*f[c]+1;    f[c] += x;}
int main() {
    scanf("%d%d", &n, &m);
    int magic = (int)sqrt((double)n+0.5);
    for (int i = 1; i <= n; i++)	scanf("%d", &col[i]), pos[i] = (i-1)/magic+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_l);
    ll tmp = 0;
    int l = 1, r = 0;
    for (int i = 1; i <= m; i++) {
        if (l > Q[i].l) {for (int j = l-1; j >= Q[i].l; j--)	add(col[j], tmp, 1);	l = Q[i].l;}
        if (r < Q[i].r)	{for (int j = r+1; j <= Q[i].r; j++)	add(col[j], tmp, 1);	r = Q[i].r;}
        if (l < Q[i].l) {for (int j = l; j < Q[i].l; j++)	add(col[j], tmp, -1);	l = Q[i].l;}
        if (r > Q[i].r) {for (int j = r; j > Q[i].r; j--)	add(col[j], tmp, -1);	r = Q[i].r;}
        if (Q[i].l == Q[i].r)	{Q[i].a = 0, Q[i].b = 1;	continue;}
        Q[i].a = tmp-(Q[i].r-Q[i].l+1), Q[i].b = (ll)(Q[i].r-Q[i].l+1)*(Q[i].r-Q[i].l);
        Q[i].reduction();
    }
    sort(Q+1, Q+m+1, cmp_id);
    for (int i = 1; i <= m; i++)	printf("%lld/%lld\n", Q[i].a, Q[i].b);
    return 0;
}