你的任务便是告诉小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必须为最简分数。（详见样例）
代码：
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<list> #include<numeric> using namespace std; #define PI acos(-1.0) #define LL long long #define ULL unsigned long long #define INF 0x3f3f3f3f #define mm(a,b) memset(a,b,sizeof(a)) #define PP puts("*********************"); template<class T> T f_abs(T a){ return a > 0 ? a : -a; } template<class T> T gcd(T a, T b){ return b ? gcd(b, a%b) : a; } template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;} // 0x3f3f3f3f3f3f3f3f // 0x3f3f3f3f const int maxn=1e5+50; struct Ask{ int L,R,id; }ask[maxn]; struct Ans{ LL fz,fm; void reduce(){//分数化简 LL d=gcd(fz,fm); fz/=d;fm/=d; } }ans[maxn]; int arr[maxn],num[maxn];//从1开始计数 int n,m,siz;//n个数，m个询问，块的大小 bool cmp(Ask a,Ask b){ if(a.L/siz!=b.L/siz) return a.L/siz<b.L/siz; else return a.R<b.R; } void solve(){ LL temp=0; mm(num,0); int L=1,R=0; for(int i=1;i<=m;i++){ while(R<ask[i].R){ R++; temp-=(LL)num[arr[R]]*num[arr[R]]; num[arr[R]]++; temp+=(LL)num[arr[R]]*num[arr[R]]; } while(R>ask[i].R){ temp-=(LL)num[arr[R]]*num[arr[R]]; num[arr[R]]--; temp+=(LL)num[arr[R]]*num[arr[R]]; R--; } while(L<ask[i].L){ temp-=(LL)num[arr[L]]*num[arr[L]]; num[arr[L]]--; temp+=(LL)num[arr[L]]*num[arr[L]]; L++; } while(L>ask[i].L){ L--; temp-=(LL)num[arr[L]]*num[arr[L]]; num[arr[L]]++; temp+=(LL)num[arr[L]]*num[arr[L]]; } ans[ask[i].id].fz=temp-(R-L+1); ans[ask[i].id].fm=(LL)(R-L+1)*(R-L); ans[ask[i].id].reduce(); } } int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;i++) scanf("%d",&arr[i]); for(int i=1;i<=m;i++){ ask[i].id=i; scanf("%d%d",&ask[i].L,&ask[i].R); } siz=(int)sqrt(n*1.0); sort(ask+1,ask+m+1,cmp); solve(); for(int i=1;i<=m;i++) printf("%lld/%lld\n",ans[i].fz,ans[i].fm); } return 0; }