分类: [分块]

莫队算法入门:小Z的袜子

先说一句:这是我的第一个算法,太菜勿喷,可在评论区答疑. Description 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命…… 具体来说,小Z把这N只袜子从1到N编号,然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。 你的任务便是告诉小Z,他有多大的概率抽到两只颜色相同的袜子。当然,小Z希望这个概率尽量高,所以他 ......

BZOJ2120 数颜色(带修改莫队)

题目大意 有n个数字,并有两种操作。 Q l r:询问l,r间不同数字的个数 R x key:将数x的值改为key Solution 如果不带修改操作,用莫队可以很好地解决问题(有蒟蒻说用主席树?),但有了修改操作,该怎么办呢? Idea 其实还是可以用莫队的。只要记录下每组询问是多少次修改之后得到的,在每次做询问前,把现在少改的修改改上,多改的改回来。具体实现呢——暴力for循环。其他都一样。 由于每次都要暴力修改,要保证复杂度,排序方式应不一样。 bool cmp(query x,query y) {//pos表示这个点所在的块 ......

SPOJ COT2 Count on a tree II

题目大意 给定一棵n个点的树,每个点有点权。有m次询问,每次查询u,v点间的链上有几种不同颜色的点。 n<=40000 m<=100000 Solution 如果这棵树是一条链,该怎么做呢?最方便的算法肯定是莫队。可以参考PhoenixGS的博客《莫队算法》Orz。它的一个小常数优化,也可以在他的博客中找到,我就不讲了。 但是树上可不可以实现呢?答案是可以的。考虑整棵树的括号序列,每个点入栈时记下它的时间戳,出栈时也记下时间戳。这样,我们可以对每组询问进行转化。 如: 其中,黑色代表入栈时间戳,红色代表出时间戳。 如果统计每组询问的 ......