OmaeWaMouShenDeiru's blog

Data structure Ideas!!
By OmaeWaMouShenDeiru, history, 9 years ago, In English

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 ??

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Rope will do just fine.

→ Reply
»
9 years ago, # |
  Vote: I like it -7 Vote: I do not like it

is there any other data structures with log(n) time insert delete and range query ??

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks, I've read the tutorial and I understood it, but I need to improve mu knowledge of BIT first.

    Thanks :D

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply