[2009国家集训队]小Z的袜子(hose)

题目上次那个有。。下面要说从fjxmlhx神牛那里知道的各种做法。。。
再结合我以前的各种做法。。有5种了T_T。。
1: 标准做法,曼哈顿最小生成树,然后遍历。。SqrtM*N+NLogN
2: 我以前的SB做法,随机一个比较小的生成树,然后遍历。。 nimendongde
3: 先将所有序列按起始点排个序,然后每次找一个结尾点的最长上升或下降序列。。
然后可以在O(N)处理掉这个序列。。每次都这么干直到没有。。
可以证明最多找SqrtM次。。所以是SqrtM*(M*LogM+N)
设一个询问左端点为l,右端点为r
设我们要计算l到r中取相同的颜色的袜子的方法数
设Ai为第i项的颜色,也就是
Size {l<=i<j<=r,Ai==Aj}
定义Ci为Size{i<j<=r,Ai==Aj}
那么我们就是要求Sum C(l..r)
4: 强大的做法来了。。我们从左往右扫描,动态维护Ci,
那么我每次加入一个点。。那些点的Ci变了呢。。就是在该点前面跟它一个颜色的点,Ci都+1了。。
那么我们可以使用树状数组来维护这个结构。。
额。。。如果一个颜色的点很多不就悲剧了么。。。
关键就是这里,如果一种颜色数量超过SqrtN。。那么我直接把这个颜色的位置存放在一个数组里。。。
那么显然可以在LogN的时间内二分出其中在l到r之间的个数。。。。
所以这些都可以忽略
然后颜色数量小于SqrtN的话,那么只要一个个更新也没事。。
复杂度N*LogN*SqrtM 常数很小。。速度很快。。。
5. 更强大的做法来了。。还是同样的考虑。。我们直接维护所有点的Ci和,不按颜色数量拆开。。
为了达成这个需要使用块状数组。。。按SqrtN分块。。每块记录这个块中所有点的Ci和。。
那么插入一个点之后,这个点之前的块的贡献和都会增加该块内与插入点同色的点的数量。。
预处理一下每个块内各种颜色的数量。。
然后询问的时候也差不多。。不过需要计算除了快之外的两端。。。
总体复杂度是N*SqrtM。。。不过空间复杂度很大而且常数也不小。。所以速度反而比第4个慢囧。。。
代码还是直接上nimendongde这个号去看吧。。
53634 是算法4
53397 是算法1
53632 是算法5
52092 是算法2
算法3没写。。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>