Hello,
This is an interesting data structure problem.
It can't be solved with regular insertion and print.
Who do you think it can be solved ??
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
Hello,
This is an interesting data structure problem.
It can't be solved with regular insertion and print.
Who do you think it can be solved ??
Name |
---|
Rope will do just fine.
it's very nice, I understood most of what I read, but I couldn't find any more tutorial's,explanations, and implementation for it.
Do you have any ??
look here: https://www.sgi.com/tech/stl/Rope.html, you can use it with some c++ compilers..
Thanks, I wanted to see full implementation but this is enough now :D
is there any other data structures with log(n) time insert delete and range query ??
Treap?
hello Just-yousef
This problem is already asked in lunch time contest on codechef. you can check this link for more details here. You can check the editorial for the detail explanation of the solution to this problem.
Here are the steps to solve this problem. 1. First find the final string after all insertion. ( Think on this ) 2. Now process queries in the reverse order and a simple rank based segment tree will help you to answer each query.
I have written just to guide you. If u find anything that is not understandable from the available editorial just reply on this thread. I will be more happy to help you.
thanks, I've read the tutorial and I understood it, but I need to improve mu knowledge of BIT first.
Thanks :D
Hello JUST_Yousef,
Have you understood the solution of this problem ? This problem was seriously one of the most interesting problem. If you got the solution correctly try this one from the codeforces discussion here