(int jobi, int l, int r, int i)
| 164 | |
| 165 | // 数值范围[l..r]，加了一个数字jobi，生成新版本的可持久化线段树 |
| 166 | public static int insert(int jobi, int l, int r, int i) { |
| 167 | int rt = ++cntt; |
| 168 | ls[rt] = ls[i]; |
| 169 | rs[rt] = rs[i]; |
| 170 | numcnt[rt] = numcnt[i] + 1; |
| 171 | if (l < r) { |
| 172 | int mid = (l + r) / 2; |
| 173 | if (jobi <= mid) { |
| 174 | ls[rt] = insert(jobi, l, mid, ls[rt]); |
| 175 | } else { |
| 176 | rs[rt] = insert(jobi, mid + 1, r, rs[rt]); |
| 177 | } |
| 178 | } |
| 179 | return rt; |
| 180 | } |
| 181 | |
| 182 | // 可持久化线段树，前版本pre，后版本post，两个版本做差，得到数值范围[l..r]的词频 |
| 183 | // 查询这个数值范围上，第jobk大的数字是什么 |