tbquan08hanoi's blog

Substring Reversal
By tbquan08hanoi, history, 3 months ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
  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
→ Reply
»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

prefix sum

→ Reply