| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
We have N balls(numbered from 1 to N) and we have 2 types of queries:
1-put ball x in front of ball y
2-print the ith ball's number
initial state: 1 2 3 4
query 1 : 1 3 1 --> 3 1 2 4
query 2 : 1 4 3 --> 4 3 1 2
query 3 : 2 2 --> 3
query 4 : 2 4 --> 2
How to perform these queries efficiently ?
I think with SQRT-decomposition you can do it in
:
Query 1: Find the bucket that contains the ball in
steps and put the ball in position inside the bucket in another 
steps. If the bucket is not the last one, get the last ball from this bucket and put in the beginning of the next bucket, so you can always have only 
items inside each bucket. You can maintain a list for fast insert/deletion in any place, so pushing a ball in front and popping back is done in O(1), and the bucket-balancing phase is done in at most 
steps as well.
Query 2: You can find the bucket that contains the position you want in either
by doing a binary search or in plain 
. Inside the bucket you run through the list in 
to find the ball you want.
Final complexity is
per query.
caioaao How do I "Find the bucket that contains the ball in root N steps" in query 1 ?
Got it by using a boolean array [rootN][N] size. Which marks what balls are present in the bucket. Thankyou.
You can also keep an array [N] marking the bucket idx for each ball, and remember to update it anytime a ball moves from one bucket to another. This way you'll find the bucket in O(1). When I wrote the answer, I thought the first query was "Put ball x in front of ith ball", that's why I thought of going through the buckets in
to insert a ball.
Looks like a basic Treap exercise
Absolutely agree , an Implicit Treap can solve that problem in O( log ( n ) ) per query.
Link
Do you have another link in english?
You can use a Web page translator(like Google Translator) or use Google Chrome to go through This page in English.
Can the queries be proceeded offline? If yes, there is a solution, which takes O(N + Q). I wanted to give this problem on my team's contest in Petrozavodsk, but I could not pick restrictions, so that only linear solutions would pass. The main idea is to copy balls instead of moving them, while storing them in a list, so that the list will contain all the previous versions of every ball. At first one can proceed all queries of the 1-st type. Then iterate through the list and for every version of every ball get its position in the list. After that, one can answer all queries of the 2-nd type.
Splay tree may solve in O(logN) average complexity per query.