简介
= = = =
经典应用
区间第 $k$ 小
Luogu P3834 【模板】可持久化线段树 2（主席树） 区间第 $k$ 小
Luogu P2617 Dynamic Rankings 带修区间第 $k$ 小
Luogu P2633 Count on a tree 树上区间第 $k$ 小
Luogu P4175 [CTSC2008]网络管理 树上带修区间第 $k$ 小
区间不同数的个数
有效利用主席树的继承
简要题意：给定一个长度为 $n$ 的序列 $a$ 和 $m$ 次询问，每次询问给定两个区间 $[l_1,r_1],[l_2,r_2]$，保证 $r_1<l_2$，求左端点在 $[l_1,r_1]$，右端点在 $[l_2,r_2]$ 的所有区间中，中位数最大的区间，询问强制在线
$n\le 20000,m\le 25000$
简要题解：对于中位数，我们考虑二分 $x$，然后令大于等于 $x$ 的数为 $1$，小于 $x$ 的数为 $-1$，那么如果区间和大于等于 $0$，则表示中位数大于等于 $x$
注意到区间不相交，那么我们二分之后，肯定选择 $[l_1,r_1]$ 的后缀最大值加 $[r_1+1,l_2-1]$ 的和加 $[l_2,r_2]$ 的前缀最大值
那么现在的问题是如何维护这些东西，注意到随着二分 $x$ 的值的变化，越来越多的 $1$ 会变成 $-1$，且一共只会变化 $O(n)$，我们可以用主席树来维护从 $x$ 变成 $x+1$ 的继承关系