| 20 | return cur; |
| 21 | } |
| 22 | int upd(int pre, int b, int e, int i, int v) { |
| 23 | int cur = ++T; |
| 24 | t[cur] = t[pre]; |
| 25 | if(b == e) { |
| 26 | t[cur].val += v; |
| 27 | return cur; |
| 28 | } |
| 29 | int mid = b + e >> 1; |
| 30 | if(i <= mid) { |
| 31 | rc = t[pre].r; |
| 32 | lc = upd(t[pre].l, b, mid, i, v); |
| 33 | } else { |
| 34 | lc = t[pre].l; |
| 35 | rc = upd(t[pre].r, mid + 1, e, i, v); |
| 36 | } |
| 37 | t[cur].val = t[lc].val + t[rc].val; |
| 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; |