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

Time Limit: 20 Sec Memory Limit: 259 MB
Submit: 11866 Solved: 5318
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

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
【样例解释】

询问1：共C(5,2)=10种可能，其中抽出两个2有1种可能，抽出两个3有3种可能，概率为(1+3)/10=4/10=2/5。
询问2：共C(3,2)=3种可能，无法抽到颜色相同的袜子，概率为0/3=0/1。
询问3：共C(3,2)=3种可能，均为抽出两个3，概率为3/3=1/1。
注：上述C(a, b)表示组合数，组合数C(a, b)等价于在a个不同的物品中选取b个的选取方案数。
【数据规模和约定】

30%的数据中 N,M ≤ 5000；
60%的数据中 N,M ≤ 25000；

莫队算法：

当我们遇到很多区间查询的题时，我们都会想到线段树或者树状数组。但是这道题并不能这么做。这时我们可以采用莫队算法。

所谓莫队算法，就是优化过后的暴力。为什么这么说呢？

当我们知道一个区间（l，r）的信息时，我们可以o（1）的时间维护处(l - 1,r)或（l + 1，r）或（l，r - 1）或（l，r + 1）的信息。

如这道题来说：在1 - n的区间里散落着不同颜色的袜子，我们知道（l，r）区间里各个袜子有多少个，当到（l - 1，r）我们只需在原来的基础上加上位于下标（l - 1）位置的袜子就行了。

然后说下莫队算法的具体操作：

先离线把所有要查询的区间按排个序：把1 - n 分块，分为sqrt（n）或 sqrt（n） + 1个区间。我们把查询的左端点所属区间作为排序第一关键值，把查询的右端点作为排序第二关键值。

当我们依次查询区间时，l 在不同区间中是单调递增的，r 在同一区间是单调递增的，当移动这两个指针近视o（n）的操作。

在同一区间中l 是无序的，不同区间中 r 也是无序的，所以暴力去移动就行了。

因为分块是sqrt（n）移动指针近似o(n) 总复杂度o（n sqrt(n））

分析：

再说说这道题，当查询一个区间时 ans = （C（a1，2） + C(a2，2） + ……C（ak，2））/ C（len，2），a1，a2……ak为各个颜色袜子在当前区间的数量，len为当前区间长度，a1 + a2 + …… ak == len;

因为C(x，2） == x * (x - 1),所以答案为 (（a1 * （a1 - 1）） + ……（ak * （ak - 1））) / len * （len - 1）；分母加上 a1 + a2 + …… ak ，即加上len变为了 a1² +a2 ² +……ak ²。

所以我们只用维护l，r里面每个袜子数量的平方和就行了，求答案时分子 - len，分母为len * （len - 1）；求个gcd通分一下即行。具体维护方法采用莫队算法

附上AC代码：

# include <iostream>

# include <cstdio>

# include <cstring>

# include <cmath>

# include <algorithm>

using namespace std;

const int N = 5e4 + ;

int n,m,a[N],tot,block[N];

long long ans,sum[N],f[N];

long long S(long long k){return k * k;}

long long Gcd(long long a,long long b){if(a < b)swap(a,b);while(b){a %= b;swap(a,b);}return a;}

struct data{

    int l,r,xh;

    long long c,d;

bool operator <(const data & other)const {

 if(block[l] == block[other.l])return r < other.r;

 return l < other.l;

}

}q[N];

bool cmp(data a,data b){

    return a.xh < b.xh;

}

void updata(int num,int l){ans -= S(sum[a[num]]);sum[a[num]] += l;ans += S(sum[a[num]]);}

int main(){

  scanf("%d %d",&n,&m);tot = sqrt(n);

  for(int i = ;i <= n;i++)scanf("%d",&a[i]),block[i] = i / tot + ;

  for(int i = ;i <= m;i++)scanf("%d %d",&q[i].l,&q[i].r),q[i].xh = i;

  sort(q + ,q + m + );

  int l = ,r = ;

  for(int i = ;i <= m;i++){

    while(l < q[i].l)updata(l,-),l++;

    while(l > q[i].l)updata(l - ,),l--;

    while(r < q[i].r)updata(r + ,),r++;

    while(r > q[i].r)updata(r,-),r--;

    if(l == r){q[i].c = ;q[i].d = ;continue;}

    q[i].c = ans - (q[i].r - q[i].l + );

    q[i].d = (long long) (q[i].r - q[i].l + ) * (long long) (q[i].r - q[i].l);

    long long k = Gcd(q[i].d,q[i].c);

    q[i].c /= k;q[i].d /= k;

  }

  sort(q + ,q + m + ,cmp);

  for(int i = ;i <= m;i++){

    printf("%lld/%lld\n",q[i].c,q[i].d);

  }

  return ;

}

袜子

[Bzoj2039]小Z的袜子 （莫队算法模板题）