varinic 的博客

把区间统计转化为前缀和，这里的前缀和不是普通的前缀和，对相同的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]来求。 这里的一个问题是前缀

这道题目其实和 spoj上的d-query 差不多  http://blog.csdn.net/mtrix/article/details/52335617， 本质都是统计连续区间不同数个数，本来有 离线+树状数组 和在线主席树 两种做法， 这里强制在线那就主席树，对每个前缀要判断它有没有出现过可以用hash也可以字典树。 #include #include #include

主席树又名可持久化线段树。 我们先撇开可持久化看看主席树是怎么实现的。维护一个长度为n的序列，我们可以建一颗线段树来维护，最上的根节点代表的区间是[1,n]。 我们知道线段树的形态由你给的[l，r]，既维护的区间长度决定，现在我要为这个序列的每一个前缀建一棵线段树，每一棵线段树最上的根节点代表的区间依然是[1,n]，所以这n棵线段树的结构是一模一样的。 这里的线段树不是普通的线段树而是权