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

Substring Reversal
Автор tbquan08hanoi, история, 3 месяца назад, По-английски

Hi Codeforces community!

I was doing a problem like this: Given a string s, reverse a substring of it in each query, and print the final string after all queries. Constraints are 1 ≤ |S|, Q ≤ 10^5. I have seen many solutions using tree algorithms, is it possible to solve this problem without using tree algorithms?

Thanks!

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

»
3 месяца назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
  1. It's actually a tree algorithm inside, but you can use __gnu_cxx::rope for this task (so you don't actually need to do anything by yourself)
  2. Default split-rebuild sqrt decomposition
→ Ответить
»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I found this code which solves CSES — Subtring Reversals using some kind of sqrt blocking

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

prefix sum

→ Ответить