题目大意 有n个数字,并有两种操作。 Q l r:询问l,r间不同数字的个数 R x key:将数x的值改为key Solution 如果不带修改操作,用莫队可以很好地解决问题(有蒟蒻说用主席树?),但有了修改操作,该怎么办呢? Idea 其实还是可以用莫队的。只要记录下每组询问是多少次修改之后得到 …
SPOJ COT2 Count on a tree II

题目大意 给定一棵n个点的树,每个点有点权。有m次询问,每次查询u,v点间的链上有几种不同颜色的点。 n<=40000 m<=100000 Solution 如果这棵树是一条链,该怎么做呢?最方便的算法肯定是莫队。可以参考PhoenixGS的博客《莫队算法》Orz。它的一个小常数优化,也 …