Description

　　小Z有很多袜子，给你一个长度为n的袜子序列，每个袜子有自己的颜色，你需要求对于任意一段区间【l，r】，任意拿一对袜子，颜色相同的概率。

分析

　　首先考虑一下答案怎么求，任意选取的方案数应该是（r-l+1）*（r-l），而取出相同颜色袜子的方案数满足加法原理，则应是Σ sum【i】*（sum【i】-1）/2，i是区间内包含的颜色。假设有a，b，c三种颜色，那么累加应该是（a-1）*a+（b-1）*b+（c-1）*c，拆开，=a^2+b^2+c^2-（a+b+c）=Σsum【i】^2 -（r-l+1）；

　　这种问题，因为涉及算的东西比较多，而且合并什么的好像不太可能，所以貌似得一个一个累计答案，而这样复杂度太高啊怎么办？离线吼啊，如果我们以l为第一关键词，r为第二关键词，把询问排序，这样是不是可以减少很多不需要的消耗啊？

版权声明：本文为kgxw0430原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/kgxw0430/p/10276152.html