tyristik's blog

Harder version of today's Div.3C
By tyristik, history, 4 months ago, In English

How to solve today's C problem if alphabet is not $$$26$$$ characters but rather $$$O(n)$$$? I could only come up with simple offline $$$O(q \sqrt n)$$$ solution using basic MO algorithm. Any ideas?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

How do you solve it in $$$\sqrt{n}$$$ per query?

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

    Mo's algorithm: you can maintain answer for segment $$$(l, r)$$$ and recalculate it in $$$O(1)$$$ when moving borders. That's basics of MO.

    → Reply