| 182 | // 可持久化线段树，前版本pre，后版本post，两个版本做差，得到数值范围[l..r]的词频 |
| 183 | // 查询这个数值范围上，第jobk大的数字是什么 |
| 184 | public static int query(int jobk, int l, int r, int pre, int post) { |
| 185 | if (l == r) { |
| 186 | return l; |
| 187 | } |
| 188 | int rsize = numcnt[rs[post]] - numcnt[rs[pre]]; |
| 189 | int mid = (l + r) / 2; |
| 190 | if (rsize >= jobk) { |
| 191 | return query(jobk, mid + 1, r, rs[pre], rs[post]); |
| 192 | } else { |
| 193 | return query(jobk - rsize, l, mid, ls[pre], ls[post]); |
| 194 | } |
| 195 | } |
| 196 | |
| 197 | public static int kthMax(int u, int x, int k) { |
| 198 | for (int p = MAXP - 1; p >= 0; p--) { |