标签为 [莫队算法] 的文章

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。它的一个小常数优化,也可以在他的博客中找到,我就不讲了。 但是树上可不可以实现呢?答案是可以的。考虑整棵树的括号序列,每个点入栈时记下它的时间戳,出栈时也记下时间戳。这样,我们可以对每组询问进行转化。 如: 其中,黑色代表入栈时间戳,红色代表出时间戳。 如果统计每组询问的 ......