题目描述
作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。
然而数据中有L=R的情况，请特判这种情况，输出0/1。
输入输出格式
输入格式：
输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。接下来一行包含N个正整数Ci，其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。再接下来M行，每行两个正整数L，R表示一个询问。
输出格式：
包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。（详见样例）
输入输出样例
输入样例#1： 复制
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6
输出样例#1： 复制
2/5
0/1
1/1
4/15
说明
30%的数据中 N,M ≤ 5000；
60%的数据中 N,M ≤ 25000；
100%的数据中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。
答案是：
(a∗(a−1)/2+b∗(b−1)/2+c∗(c−1)/2....)/((R−L+1)∗(R−L)/2)
化简一下:
(a2+b2+c^2+……-(a+b+c+……))/(R-L+1)(R-L)
那么就是
(a2+b2+c^2+……-(R-L+1))/(R-L+1)(R-L)
我们愉快的这个题变成了上一个题； 不一样的地方就是统计答案时，不能用一个数组了，要再开一个结构体，一个存分子，一个存分母；再化简，特判，long long 就差不多了；
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define rg register
#define ll long long
using namespace std;
inline char gc()
{
static char BB[1000000],*S=BB,*T=BB;
return S==T&&(T=(S=BB)+fread(BB,1,1000000,stdin),S==T)?EOF:*S++;
}
inline int read()
{
rg int x=0;rg char ch=gc();
while(ch<48)ch=gc();
while(ch>=48)x=x*10+(ch^48),ch=gc();
return x;
}
int wt[30];
inline void putout(long long x)
{
if(!x){putchar(48);return;}
register int l=0;
while(x)wt[++l]=x%10,x/=10;
while(l)putchar(wt[l--]+48);
}
struct node{
int l,r,id;
ll len;
}b[60010];
int a[60010],pos[60010],n,m,ki,num[60010];
ll ans1[60010],ans2[60010],tot;
inline ll gcd(ll x,ll y) {return !y?x:gcd(y,x%y);}
inline bool cmp(node a,node b){
if (pos[a.l]<pos[b.l]) return 1;
else return 0;
if (pos[a.l]&1) return a.r<b.r;
return a.r>b.r;
}
inline void add(int x){
tot+=((num[x]<<1)|1),num[x]++;
}
inline void rem(int x){
tot+=1-(num[x]<<1),num[x]--;
}
void init(){
n=read(),m=read();
ki=n/sqrt((m<<1)/3);
for (rg int i=1;i<=n;i++) a[i]=read();
for (rg int i=1;i<=m;i++){
b[i].l=read(),b[i].r=read();
b[i].len=b[i].r-b[i].l+1,b[i].id=i,ans2[i]=1,pos[i]=(i-1)/ki+1;
}
}
void doit(){
sort(b+1,b+m+1,cmp);
int l=b[1].l,r=b[1].r;
for (rg int i=l;i<=r;i++) add(a[i]);
ll fz,fm,g;
if (tot!=b[1].len){
fz=tot-b[1].len,fm=b[1].len*(b[1].len-1),g=gcd(fz,fm);
ans1[b[1].id]=fz/g,ans2[b[1].id]=fm/g;
}
for (rg int i=2;i<=m;i++)
{
while(l<b[i].l) rem(a[l++]);
while(l>b[i].l) add(a[--l]);
while(r>b[i].r) rem(a[r--]);
while(r<b[i].r) add(a[++r]);
if(b[i].len!=tot)
{
fz=tot-b[i].len,fm=b[i].len*(b[i].len-1);
g=gcd(fz,fm),ans1[b[i].id]=fz/g,ans2[b[i].id]=fm/g;
}
}
for(register int i=1;i<=m;i++) putout(ans1[i]),putchar('/'),putout(ans2[i]),putchar(10);
}
int main(){
init();
doit();
return 0;
}