
主席树
varinic
这个作者很懒,什么都没留下…
展开
-
spoj D-query 区间不同数个数 主席树||离线+树状数组
把区间统计转化为前缀和,这里的前缀和不是普通的前缀和,对相同的ai,只有最右边那个才是有效的。 举个栗子:1 2 2 1 3 这样一个序列有效是这个样子 * * 2 1 3 ,因为1在后面出现过所以前一个无效,同理 2。前缀和则是0 0 1 2 3 ,那么对区间[1,5],[2,5],[3,5],[4,5],..[x,5] 我们都可以用sum[5]-sum[x-1]来求。 这里的一个问题是前缀原创 2016-08-27 16:45:25 · 2334 阅读 · 0 评论 -
hdu 5790 prefix 主席树
这道题目其实和 spoj上的d-query 差不多 http://blog.csdn.net/mtrix/article/details/52335617, 本质都是统计连续区间不同数个数,本来有 离线+树状数组 和在线主席树 两种做法, 这里强制在线那就主席树,对每个前缀要判断它有没有出现过可以用hash也可以字典树。 #include #include #include原创 2016-09-01 18:07:07 · 884 阅读 · 0 评论 -
主席树 poj 2104 K-th Number
主席树又名可持久化线段树。 我们先撇开可持久化看看主席树是怎么实现的。维护一个长度为n的序列,我们可以建一颗线段树来维护,最上的根节点代表的区间是[1,n]。 我们知道线段树的形态由你给的[l,r],既维护的区间长度决定,现在我要为这个序列的每一个前缀建一棵线段树,每一棵线段树最上的根节点代表的区间依然是[1,n],所以这n棵线段树的结构是一模一样的。 这里的线段树不是普通的线段树而是权原创 2016-08-26 17:55:45 · 673 阅读 · 0 评论