HYSBZ

B - 小Z的袜子(hose)

题意：

　　给出一个n双袜子颜色（不同的数值代表不同的颜色），问在【l，r】区间内挑选袜子，袜子颜色相同的概率是多少？（要求答案为最简分数）

分析：

　　为了方便，首先假设某个子区间【L，R】内一共有三张颜色不同的袜子，袜子数量分别为a，b，c，显然可知，我们所求的概率P=（C（a，2）+C（b，2）+C（c，2））/C（a+b+c，2）。C（a+b+c，2）= （R-L）*（R-L+1）/ 2（a+b+c=R-L+1），C（a，2）+C（b，2）+C（c，2）=a*（a-1）/ 2 + b*（b-1）/ 2 + c*（c-1）/ 2 =(a^2+b^2+c^2) / 2 - (a+b+c) / 2 = (a^2+b^2+c^2) / 2 - (R-L+1) / 2。化简后，P=（ (a^2+b^2+c^2) - (R-L+1) ) / （ (R-L) * (R-L+1) ）。

　　对于分子，因为R-L+1是定值，所以我们只需要维护元素个数的平方对答案的贡献就好了，每次我们在add或者del某个元素的个数时，只需要减去之前这个值的个数对答案的贡献，在加上这个值新的个数对答案的贡献，最后得出的就是a^2+b^2+c^2……

代码：

#include <map>
#include <queue>
#include <math.h>
#include <string>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std;
#define ll long long
#define ull unsigned long long
#define cls(x) memset(x,0,sizeof(x))
#define clslow(x) memset(x,-1,sizeof(x))

const int maxn=5e4+100;

ll num;
int n,q,block_size;

int arr[maxn],cnt[maxn];
ll res[maxn],all[maxn];

struct Query {
    int l,r,id;
    bool operator < (const Query& rhs) const {
        if(l/block_size!=rhs.l/block_size){
            return l/block_size<rhs.l/block_size;
        }
        return r<rhs.r;
    }
};
Query query[maxn];

void add(int pos)
{
    num-=cnt[arr[pos]]*cnt[arr[pos]];
    cnt[arr[pos]]++;
    num+=cnt[arr[pos]]*cnt[arr[pos]];
}

void del(int pos)
{
    num-=cnt[arr[pos]]*cnt[arr[pos]];
    cnt[arr[pos]]--;
    num+=cnt[arr[pos]]*cnt[arr[pos]];
}

int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        num=0;
        cls(cnt);
        block_size=sqrt(n);

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

        sort(query+1,query+q+1);
        int L=query[1].l,R=L-1;
        for(int i=1;i<=q;i++){
            while(L>query[i].l) add(--L);
            while(L<query[i].l) del(L++);
            while(R<query[i].r) add(++R);
            while(R>query[i].r) del(R--);
            res[query[i].id]=num-(R-L+1);
            all[query[i].id]=(ll)(R-L)*(R-L+1);
        }

        for(int i=1;i<=q;i++){
            ll gcd=__gcd(res[i],all[i]);
            printf("%lld/%lld
",res[i]/gcd,all[i]/gcd);
        }
    }
    return 0;
}