k -th sorted element in cur segment tree
| 58 | } |
| 59 | //k -th sorted element in cur segment tree |
| 60 | int query(int cur, int b, int e, int k) { |
| 61 | if(b == e) return b; |
| 62 | int lsz = t[lc].sz; |
| 63 | int mid = b + e >> 1; |
| 64 | if(k > lsz) return query(rc, mid + 1, e, k - lsz); |
| 65 | return query(lc, b, mid, k); |
| 66 | } |
| 67 | } t; |
| 68 | bool ty[N]; //0 - inc; 1 - dec |
| 69 | //i-th pos store a substr (l, r) such that l = i (if exists) |