sitingfake's blog

DSU roll back offline deletion
By sitingfake, history, 4 weeks ago, In English

can anyone help me explain this technique, is this technique used frequently in famous contests such as icpc,ioi...? sorry for my poor english

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

»
4 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

Just take the advice from Um_nik: "Stop learning useless algorithms, go and solve some problems, learn how to use binary search".

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    There's no need to take some algos down. DSU roll back offline deletion is also a common and useful algo with widely use. It's easy, too. Just use a stack to record the operations and pop while you need to roll back, which is much shorter than sustainable DSU.
    I think Um_nik's words are not right at all. On one hand, for example, in China, it's necessary to use some "useless algorithms" like Li-Chao Segment Tree, Segment Tree Beats and $$$k$$$-th shortest path expertly for the OIers who's just a junior high school with about 14 years old. MST in $$$O(E\log V)$$$ is one of the key tools for 12 year-old kids to get more points in the CSP Coding ability recognization. On the other hand, Codeforces is not the only OJ all around the world, although it has the most valuable problems. Many CPers spend their time on other OJ, maybe AtCoder for Japanese, Luogu for Chinese, or others. The color of the name on CF is not the only evidence to judge a CPer's ability.
    Uselessness is not the excuse of laziness. Keeping learning is the most fun thing in the life.

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      My answer was mostly to this part of the question: "is this technique used frequently in famous contests such as icpc,ioi."

      I believe there's very limited usefulness to learn advanced algorithms while more simple algorithms are not mastered.

      "The color of the name on CF is not the only evidence to judge a CPer's ability." — I strongly disagree with this claim. It might be true if the user has too few contests but if one participated in, let's say, 10 contests — then we can reliably judge his/her ability.

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

to enable rollbacks in any data structure, we can simply save every change invector<pair<int&, int>>, where first element in pair is link to changed memory, and second — value before change.When we need to undo last change, just changes.back().first = changes.back().second;changes.pop_back(); remember, that in dsu you change multiply values in one query, so we need to undo a couple of changes to make rollback.

→ Reply