BZOJ2038 小Z的袜子 <莫队>

Problem

小Z的袜子

Description

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

Input

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

Output

包含行，对于每个询问在一行中输出分数表示从该询问的区间中随机抽出两只袜子颜色相同的概率。若该概率为则输出，否则输出的必须为最简分数。

Sample Input

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

Sample Output

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

Hint

样例解释
询问：共种可能，其中抽出两个有种可能，抽出两个有种可能，概率为。
询问：共种可能，无法抽到颜色相同的袜子，概率为。
询问：共种可能，均为抽出两个3，概率为。
数据规模和约定
的数据中 ；
的数据中 ；
的数据中 ，，。

标签：莫队

Solution

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

Code

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