解题报告 SPOJ DQUERY D-query(主席树)解题报告 解题思路本题是要求区间内不同数的个数,这是主席树的常见应用之一了。做法很简单,我们可以倒序(从右向左)建立主席树,如果一个值还没出现过,则直接插入,否则删除后再重新插入(相当于保留这个数最左出现的位置)。之后要查询 [l, r] 时,选用 l 位置的主席树,这时树中的数据是 [l, n] 范围内的,因此查询时需要传入 r 作为挡板,仅统计小于等于 r 的个数,这样就可以实现 [l, r] 区间不同数的查询。当然也可以保留每个数最右出现的位置来正序建树,和上面的做法就反过来了。 阅读全文 2017-09-25 2,128 次浏览 0 条评论
解题报告 SPOJ COT Count on a tree(主席树+LCA)解题报告 解题思路主席树的区间第 K 大的树上版本。从根结点到每个结点都建立一个版本的线段树即可。查询时 a 到 b 路径时需要按照 $root[a] + root[b] - root[lca(a,b)] - root[fa[lca(a,b)]]$ 计算。 阅读全文 2017-09-24 2,546 次浏览 0 条评论
解题报告 HDU 4417 Super Mario(主席树)解题报告 解题思路题目要求查询区间内小于等于 H 的数的个数。很显然的主席树,建树之后直接在目标区间的主席树内将 H 作为挡板递归计数即可。另外此题还可以用离线树状数组求解。 阅读全文 2017-09-24 3,219 次浏览 0 条评论
解题报告 HDU 3966 Aragorn's Story(树链剖分+线段树)解题报告 解题思路本题概括起来有两种操作:更新路径上点权查询点权树链剖分之后用线段树处理区间更新和单点查询即可(用树状数组应该会更简单一些)。 阅读全文 2017-08-21 2,691 次浏览 0 条评论
解题报告 POJ 2763 Housewife Wind(树链剖分+线段树)解题报告 解题思路本题只有两种操作:求树上两点间路径的权值和、修改边权。于是使用树链剖分就很简单了。 阅读全文 2017-08-19 3,349 次浏览 0 条评论