| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3947 |
| 2 | ecnerwala | 3654 |
| 3 | jiangly | 3627 |
| 4 | jqdai0815 | 3620 |
| 5 | orzdevinwang | 3612 |
| 6 | Benq | 3586 |
| 7 | Radewoosh | 3582 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | ksun48 | 3474 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 163 |
| 2 | maomao90 | 160 |
| 3 | adamant | 156 |
| 4 | atcoder_official | 154 |
| 5 | maroonrk | 153 |
| 6 | -is-this-fft- | 148 |
| 6 | SecondThread | 148 |
| 8 | Petr | 147 |
| 9 | nor | 145 |
| 10 | cry | 144 |
There are N numbers(1 to N), arranged in increasing order. There are q operation that has to be performed on permutation. In ith operation, we'll have Li, Ri(two indices) and we have to reverse the permutation from arr[Li] to arr[Ri]. At last, after performing all operations, we have to return value at kth position.
N<=10^9
q<=10^5
1<= Li, Ri <=N
k<=N
Auto comment: topic has been updated by _amit.nehra_ (previous revision, new revision, compare).
Link to the question?
It was in Online Assessment of SAP LAB, so I don't have the question itself.
I think i have done similar question using Treap data structure.
unfortunately I can't help you :_(
You can use treap or splay tree.
You can use treaps as others have said but since this is from an OA, treap is definitely not the intended solution.
lets say after q queries x is at position k, then doing the q queries again in reverse would take x back to position x since it's a permutation. So what we can do is reverse query array and then find at what index k will be after q queries and this can be done quite easily. that index will be our answer.
Thanks man, it was brilliant