P4137 Solution
考虑建主席树:权值线段树的叶子维护这个权值最后出现的下标,push_up
的时候取 \(\min\)。
这样一个区间的 \(\min\) 小于 \(k\) 意味着有一个权值最后出现的下标小于 \(k\),也就是说 \(k\) 后面没有出现这个权值。
也就是说 mex 就在这个区间内。
这样询问的时候就可以直接在 \(r\) 的权值树内根据 \(l\) 进行二分。
时空均为 \(\mathcal O(n\log n)\),也可以改成扫描线维护一棵权值树,空间降到 \(\mathcal O(n)\)。
标签:下标,min,solution,权值,mathcal,p4137 From: https://www.cnblogs.com/iorit/p/18046109