Блог пользователя towersfreak2006

Binary Search and Deletions?
Автор towersfreak2006, 4 недели назад, По-английски

I'm looking for a data structure or subroutine that takes in a sorted list $$$L$$$ of $$$n$$$ integers and a list $$$Q$$$ of $$$n$$$ integers. For each element $$$q\in Q$$$, we should report the largest remaining element in $$$L$$$ smaller than $$$q$$$ and then remove it (or we can report $$$-1$$$ if no such integer exists). I would like the entire process to take $$$O(n \log n)$$$ time.

My understanding is that this approach is necessary for today's 2254E - Chronostasis, but many user-accepted Python solutions seem to implement Fenwick trees, which I believe might be too complicated for a Div. 3 contest and not the intended solution (though I could be wrong).

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 недели назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

dsu i guess

→ Ответить
»
4 недели назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

std::multiset can do this.

multiset<int> st;

int query(int x) {
    auto it = st.lower_bound(x);
    if (it == st.begin()) return -1;
    --it;
    int res = *it;
    st.erase(it);
    return res;
}
→ Ответить
  • »
    »
    4 недели назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Hm, do you know if there's a similar data structure in Python?

    → Ответить
    • »
      »
      »
      4 недели назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      If I am not mistaken, Python does not have built-in structures similar to std::set or std::multiset unless you use external libraries (which isn't possible on Codeforces). I would recommend either solving the problem with a different language like C++, or if you really want to remain Python-only, you can implement something similar for your specific use case.

      For this specific scenario you provided, I would recommend either of the following:

      • Implicit/Dynamic Segment Tree — For this one, you can either implement a lower_bound function with binary search and query in log^2(n), or you can implement the search in the tree propagation itself in log(n) time, depending on whether you're willing to somewhat understand the tree structure rather than black-box it.

      Not sure if there is something easier for pure Python; would be curious to hear if there is, though.

      → Ответить
»
4 недели назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

U need to use binary search + multiset, multiset supports deletions in O(log n).

→ Ответить