Блог пользователя OmaeWaMouShenDeiru

Data structure Ideas!!
Автор OmaeWaMouShenDeiru, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Rope will do just fine.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Thanks :D

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить