| 38 | return cur; |
| 39 | } |
| 40 | int query(int pre, int cur, int b, int e, int k) { |
| 41 | if(b == e) return b; |
| 42 | int cnt = t[lc].val - t[t[pre].l].val; |
| 43 | int mid = b + e >> 1; |
| 44 | if(cnt >= k) return query(t[pre].l, lc, b, mid, k); |
| 45 | else return query(t[pre].r, rc, mid + 1, e, k - cnt); |
| 46 | } |
| 47 | } t; |
| 48 | |
| 49 | //the code returns k-th number in a range l to r if the range were sorted |