When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Libraion's blog

By Libraion, history, 4 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

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

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

  • »
    »
    4 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.

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

Nobody can help me ? :(

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

What exactly don't you understand?

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

    Could you suggest me some problems of this type?

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

      Problems in Arpa's tutorial are enough

»
4 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.

»
4 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 → ><