题意：中文题
思路：经典的，莫队算法了。
对于L,R的询问。设其中颜色为x,y,z....的袜子的个数为a,b,c。。。那么答案即为(a*(a-1)/2+b*(b-1)/2+c*(c-1)/2....)/((R-L+1)*(R-L)/2)化简得:(a^2+b^2+c^2+...x^2-(a+b+c+d+.....))/((R-L+1)*(R-L))
上面组合数的化简来自 （我没化出来。。。TOT）
所以就只要统计区间内每个数出现的次数就可以了
复杂度的问题。
在所有询问中，R是单调递增的，也就是R在整个离线求解过程中只会跑一遍，L在最坏的情况下是在一个块内来回跑，因为有sqrt(n)块，每块的长度是sqrt(n)，所以L最坏的情况下是nsqrt(n)
AC代码：
#include "iostream"#include "string.h"#include "stack"#include "queue"#include "string"#include "vector"#include "set"#include "map"#include "algorithm"#include "stdio.h"#include "math.h"#pragma comment(linker, "/STACK:102400000,102400000")#define ll long long#define endl ("\n")#define bug(x) cout< <<" "<<"UUUUU"< q[i].r){ del(R--); } while(L > q[i].l){ add(--L); } while(L < q[i].l){ del(L++); } ans[q[i].id].a=temp - (R-L+1); ans[q[i].id].b=(R-L+1)*(R-L); ans[q[i].id].reduce(); } }}Mo;int main(){ scanf("%d %d", &n,&m); for(int i=1; i<=n; ++i){ scanf("%d",&a[i]); } for(int i=1; i<=m; ++i){ scanf("%d %d",&Mo.q[i].l,&Mo.q[i].r); Mo.q[i].id=i; } unit=(int)sqrt(n); sort(Mo.q+1, Mo.q+1+m); Mo.work(); for(int i=1; i<=m; ++i){ printf("%lld/%lld\n",Mo.ans[i].a, Mo.ans[i].b); } return 0;}
