BZOJ 2038
思路：
每次查询区间L，R内的两个相同颜色的袜子出现的概率，
就是区间L，R内任选两个袜子，所有情况的数量为len*（len-1）（len表示这个区间内的所有元素的个数），也就是分母。
记录每个不同颜色出现的次数为num[i]，然后统计区间[l,r]内的所包含所有的不同颜色出现的次数的平方和减去len，
就是这个区间内所有不同颜色的组合，也就是分子（可以推导一下，假设区间内的一个颜色的数量为n1，任选两这种颜色的次数为n1*（n1-1）次，然后统计这个区间内的所有不同颜色求和，就得到∑ni*ni-∑ni = ∑ni*ni-len。）
可以先求解一个区间[L,R]内的相同颜色的袜子出现的次数，
通过修改L，R，用这个次数去推导其他区间的相同颜色的袜子出现的次数。
eg：
（1）[L,R]->[L+1,R]
L前进了，区间缩小了，所以先减去L位置的颜色出现的次数的平方：
ans -= num[col[L]]^2.
，然后修改L位置的颜色出现的次数：
num[col[L]]--;
然后再给ans+新的L位置的颜色出现的次数的平方。
ans += num[col[L]]^2;
（2）区间[L,R]->[L-1,R];
L的范围扩大了，对L-1位子的颜色进行操作：
ans -= num[col[L-1]]^2.
，然后修改L-1位置的颜色出现的次数：
num[col[L-1]]++;
然后再给ans+新的L-1位置的颜色出现的次数的平方。
ans += num[col[L-1]]^2;
（3）区间[L,R]->[L,R-1];
就是右端点R进行操作进行-1操作，区间减小；
（4）区间[L,R]->[L,R+1];
对区间R+1进行操作进行+1操作，区间扩大；
然后每次更新求出分子A，分母B。
但是直接用以上方法求解的话复杂度大，所以可以将所有查询的区间按照递增的方式排序，
对n个数字的位置划分为unit个区域，然后分别按照每个查询的左端点，右端点所属的区间进行排序，原因见这篇文章。
unit = sqrt（n）。
所以最终的复杂度为O(n*sqrt(n))。
注意：结果要用longlong。
代码：
代码参考文章
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int maxn = 1e5+10; typedef long long LL; LL A[maxn],B[maxn],ans = 0;//分别记录分子，分母，ans表示所有重复数字的平方和 struct Node{ int id,l,r; }cur[maxn]; int qu[maxn]={0},col[maxn]={0},num[maxn]={0};//col记录颜色，qu将n个颜色划分为unit个不同的区块，num记录每种颜色的数量。 LL Gcd(LL x,LL y){ return y?Gcd(y,x%y):x; } bool cmp(Node a,Node b){ //将所有记录的左右边界所属的不同区块划分 if(qu[a.l]==qu[b.l]) return a.r<b.r; return a.l<b.l; } LL f(LL x){ return x*x; } void Add(int x,int d){ ans -= f(num[col[x]]); num[col[x]] += d; ans += f(num[col[x]]); } int main(void) { int n,m; scanf("%d%d",&n,&m); int unit = sqrt(n); for(int i=1;i<=n;i++){ scanf("%d",&col[i]);qu[i] = i/unit+1; } for(int i=1;i<=m;i++){ scanf("%d%d",&cur[i].l,&cur[i].r);cur[i].id = i;//离线记录每次询问的左右区间，每次询问的id } sort(cur+1,cur+1+m,cmp);//将询问分区 int l = 1,r = 0;//起始的区间，ans = 0，因为没有符合要求的数据存在。 for(int i=1;i<=m;i++){ if(cur[i].l==cur[i].r){ //特殊情况的判断，只能选一个，结果为0 A[cur[i].id] = 0;B[cur[i].id] = 1;continue; } while(l<cur[i].l){ //左区间左移更新 Add(l,-1);l++; } while(l>cur[i].l){ //左区间右移更新 Add(l-1,1);l--; } while(r<cur[i].r){ //右区间左移更新 Add(r+1,1);r++; } while(r>cur[i].r){ //右区间右移更新 Add(r,-1);r--; } //以上的区间更新的过程的同时不断更改这个区间内符合要求的ans，（ans-区间大小就是这个区间内符合要求的分子数）。 A[cur[i].id] = ans - (cur[i].r-cur[i].l+1); B[cur[i].id] = 1LL*(cur[i].r-cur[i].l+1)*(cur[i].r-cur[i].l); LL gcd = Gcd(A[cur[i].id],B[cur[i].id]);//求公约数，化简分数。 A[cur[i].id] /= gcd; B[cur[i].id] /= gcd; } for(int i=1;i<=m;i++) printf("%lld/%lld\n",A[i],B[i]); return 0; }
