Libraion's blog

[Help] Smaller-to-larger Technique

By Libraion, history, 5 years ago, In English

Recently, I have been searching for some articles about "Smaller to larger" technique on Google, but ended up finding nothing really useful (only the first 2 pages mention about it but they are all about Sack(dsu on tree) :> ...).

So could you guys show me some good documents about that technique and provide me as many as problems you guys have come across during your coding journey? <3

P/s: or share your way of understanding and applying this technique, if you could <3.

Thanks so much and have a great day <3.

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The only "document" you need https://mirror.codeforces.com/blog/entry/44351

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Can you suggest anything else? Because that article doesn't focus on explaining the smaller_to_larger I think.

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

Nobody can help me ? :(

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

What exactly don't you understand?

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

    Could you suggest me some problems of this type?

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

      Problems in Arpa's tutorial are enough

      → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Some people call this technique Sack or dsu on tree. Arpa's blog doesn't explain the technique but shows some ways to code it. I think people that don't know HLD may have a hard time understanding why the technique is fast.

Try to understand the codes, there are also a bunch of questions answered on comments.

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

Do you think dsu on tree and Smaller to larger is not the same :>

About my way of understand → ><

→ Reply