wet_water's blog

Segment Tree of DSUs
By wet_water, history, 5 years ago, In English

Hello all,

Are there any good (yet basic) problems that use a segment tree of dsus? I've been reading a lot of problem tutorials that use this as the solution, but I don't really understand how it works. I was hoping to start out with simpler problems and gradually work to the harder problems.

However, when I tried searching the topic up on google, the closest thing I could find was an article that briefly mentioned combining segment trees and dsus but failed to explain it for a beginner.

The example problem is here: https://codeforces.net/contest/763/problem/E

Any recommendations would be greatly appreciated!

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

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

can you share the problem whose editorial you were trying to read. because i know only one problem 76-A that uses segment tree of dsu

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

    [Comment Edited]

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

      And how this problem can be solved using Segment tree of DSU? ( about problem in blog 763D)

      I even don't understand why you think that it is possible.

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

Auto comment: topic has been updated by wet_water (previous revision, new revision, compare).

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

1140F? Sorry for my bad English, I don't know what data structure you are talking about.

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

    No worries, this looks like a similar problem.

    Thanks for the response!

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

Another one: 811E - Vladik and Entertaining Flags.

It has similar difficulty though

→ Reply