1function build(l, r) {
2 const id = nodes.length;
3 nodes.push({ sum: 0, l: -1, r: -1 });
4 if (l < r) { const m = (l+r)>>1;
5 nodes[id].l = build(l, m); nodes[id].r = build(m+1, r); }
6 return id;
7}
8function update(prev, l, r, pos) { // 路径复制
9 const id = nodes.length;
10 nodes.push({ ...nodes[prev], sum: nodes[prev].sum + 1 });
11 if (l < r) { const m = (l+r)>>1;
12 if (pos <= m) nodes[id].l = update(nodes[prev].l, l, m, pos);
13 else nodes[id].r = update(nodes[prev].r, m+1, r, pos); }
14 return id;
15}
16function query(u, v, l, r, k) { // 第 k 小
17 if (l === r) return l;
18 const m = (l+r)>>1;
19 const cnt = nodes[nodes[v].l].sum - nodes[nodes[u].l].sum;
20 if (k <= cnt) return query(nodes[u].l, nodes[v].l, l, m, k);
21 return query(nodes[u].r, nodes[v].r, m+1, r, k - cnt);
22}