04 2016-10 HDU 5919 Sequence II (主席树) 紫杉 主席树 2016-10-04 2,237 题目链接:点我~~ 题意:给定一个序列n,有m次查询,每次查询一个区间[l,r],求区间中每一种数在区间中第一次出现的位置的中位数,强制在线。 思路: 主席树维护后缀[i,n],然后对于每次碰到一个数字,就把它以前的位置−1,新位置+1 主席树维护区间不同数字的个数k 然后寻找区间第k/2大呗 因为是维护的后缀,直接找root[l]里的第k/2大出现的位置就... 主席树主席树 10月04日 2,237