主席树

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