[BZOJ2038]小Z的袜子（莫队算法）

分析：莫队算法

莫队算法是一种思想……

处理问题：不带修改的区间询问

使用要求：[l-1,r] [l,r-1]的结果可由[l,r]的答案在O(1)或O(logn)的时间内推出

具体步骤：

　　1、对整个区间轴分成根号n块

　　2、以l所在的块的编号为第一关键字，r为第二关键字给所有询问排序方便处理

　　3、对于每个块内的询问单独处理

　　　　①对于当前块里的第一个询问暴力求解

　　　　②剩下的在第一个询问基础上递推得到

那么对于本题，只要说明如何从[l,r]的答案推到[l-1,r] [l,r-1]就行了

注意题目最后求的是概率，那么我们不妨推种类，概率最后除以总数就行了

假设对于某个块，第一个询问[l,r]我们已经解决，且完成了这个询问的col[]数组(col[i]表示第i种颜色出现的次数）

那么考虑区间[l-1,r]，假设第i-1位的颜色为k，那么ans[l-1,r]=ans[l,r]+添加一个颜色k多的种类

那么这个东西是多少呢，其实就是C(col[k]+1,2)-C(col[k],2)=col[k]啦

对于[l,r-1]就是减了啊……完美解决了……

总结：对于那成堆的无修改的区间问题，可以先考虑莫队算法啦……即使数据结构可以破，但是绝壁没莫队算法好！（其实是代码短~\(≧▽≦)/~啦啦啦）

巴特西