$\text{🌱 Dynamic Median}$

---

🔗 Link: https://oj.vnoi.info/problem/medquery

📌 Tags: Template, Data Structure

👤 Writter: @CQTshadow

👥 Contributor: @SPyofgame

📋 Content:

• Nhận xét
• Hướng dẫn
  • I. Giải quyết bài toán
    • 1. Bản chất
    • 2. Cài đặt
  • II. Cải Tiến
    • 1. Cải Tiến Thao Tác Xóa
    • 2. Cải Tiến Xuất
• Code Minh Họa

---

Nhận xét

• Bài toán tưởng chừng khá quen thuộc, nhưng nếu code không cẩn thận thì sẽ vẫn bị
  $TLE$ vì test khá mạnh.
• Có rất nhiều cách để giải quyết bài toán này, ở đây tôi sẽ cung cấp cho các bạn cách làm sử dụng
  $2$ tập hợp.

Hướng dẫn

I. Giải quyết bài toán

1. Bản chất

• Bản chất chính, ta sẽ chia tập hợp đề bài của ta thành
  $2$ và duy trì
  $2$ tập hợp đó sao cho phần tử lớn nhất của tập hợp nhỏ hơn là
  $median$ của chúng ta :
  • Giả sử tập hợp của chúng ta là
    $S=\{s_1,s_2,...,s_k\}$
  • Tập hợp
    $Small$ : Lưu trữ các phần tử có vị trí thuộc khoảng
    $[1,\lfloor \frac{k+1}{2}\rfloor ]$
  • Tập hợp
    $Big$ : Lưu trữ các phần tử có vị trí thuộc khoảng
    $[\lfloor \frac{k+1}{2}\rfloor +1,k]$

$⟹$ Để duy trì như yêu cầu, ta chỉ cần đảm bảo

$0\le Smal{l}_{size}-Bi{g}_{size}\le 1$

2. Cài đặt

• Ta có thể dùng CTDL
  $std::set$ hoặc bất kỳ CTDL nào phù hợp với cách cài đặt.

a. Thao Tác Cân Bằng

• Như đã nói, ta cần duy trì sự cân bằng của
  $2$ tập hợp trên, do đó chỉ có
  $2$ trường hợp sai cần phải thay đổi :
  • Trường hợp 1 :
    $Smal{l}_{size}>Bi{g}_{size}+1$
    
    $⟹$ Khi đó ta lấy phần tử lớn nhất ở tập hợp
    $Small$ thêm vào tập hợp
    $Big$
  • Trường hợp 2 :
    $Smal{l}_{size}<Bi{g}_{size}$
    
    $⟹$ Khi đó ta lấy phần tử bé nhất ở tập hợp
    $Big$ thêm vào tập hợp
    $Small$
• Ta sẽ thêm thao tác này sau mọi thao tác thay đổi khác.

Code

void Balance() {
    if(sizSmall > sizBig + 1) {
        Big.push(Small.top()), sizBig++;
        Small.pop(), sizSmall--;
    }
    else if(sizSmall < sizBig) {
        Small.push(Big.top()), sizSmall++;
        Big.pop(), sizBig--;
    }
}

b. Thao Tác Thêm

• Ta cần xác định sẽ thêm phần tử
  $x$ mới vào tập hợp nào.
• Gọi
  $median$ là trung vị hiện tại của chúng ta, như đã nói nó sẽ là phần tử lớn nhất của tập hợp
  $Small$.
• Khi đó như cách ta sắp xếp hai tập hợp:
  • Nếu phần tử
    $x$ có giá trị lớn hơn
    $median$
    
    $⟹$ Ta thêm nó vào tập hợp
    $Big$.
  • Ngược lại
    
    $⟹$ Ta thêm nó vào tập hợp
    $Small$.

Lưu ý : Nhớ xét riêng trường hợp

$Small$ rỗng

Code

void add() {
    if(Small.empty()) Small.push(x), sizSmall++;
    else {
        int median = Small.top();
        if(x > median) Big.push(x), sizBig++;
        else Small.push(x), sizSmall++;
    }
    Balance();
}

c. Thao Tác Xóa

• Ta có thể đơn giản sử dụng các lệnh tìm kiếm có sẵn ở trong CTDL đang sử dụng để tìm phần tử
  $x$ cần xóa xuất hiện ở đâu trong tập hợp sau đó xóa nó.

d. Thao Tác Tìm Trung Vị

• Ta chỉ cần gọi phần tử lớn nhất của tập hợp
  $Small$.

II. Cải Tiến

• Tưởng chừng như cách giải quyết trên đã đủ để AC, nhưng test lại đủ mạnh để khiến cho ta bị TLE, do đó ta cần các cải tiến.

1. Cải Tiến Thao Tác Xóa

• Nhìn nhận điều đặc biệt mà bài toán cho ta, ta thấy số
  $x$ mà đề yêu cầu xóa luôn tồn tại trong tập hợp
  $⟹$ Ta có thể lưu lại và xóa đi các phần tử cần xóa sau.
• Thật vậy, khi ta đã xác định phần tử giá trị
  $x$ nằm ở tập hợp nào, thì ta chỉ cần ghi nợ phần tử đó vào tập hợp, và trong các quá trình thao tác trong tương lai, nếu ta phát hiện phần tử đáng ra đã bị xóa thì ta sẽ xóa nó đi mà không ảnh hưởng tới các thao tác khác.
• Mục đích chính của việc lưu nợ này lại là vì ta sẽ đợi các phần tử cần xóa mà hiện tại đang ở giữa đâu đó trong
  $2$ tập hợp chính (khiến việc xóa mất
  $O(lo{g}_{2}n)$) xuất hiện ở đầu
  $2$ tập hợp (việc xóa chỉ mất
  $O(1)$)
• Ta sẽ ghi nợ bằng cách tạo một tập hợp với thứ tự sắp xếp tương tự tập hợp ta đang nợ, và các tập hợp này sẽ chỉ lưu đúng các giá trị chưa được xóa, và sau mọi thao tác thay đổi, ta sẽ gọi thao tác trả nợ này ra để xem xem có phần tử nào cần xóa đã xuất hiện ở hai đầu tập hợp hay chưa, và nếu có thì xóa chúng đi.

Lưu ý : Ta sẽ cần phải có một giá trị quản lý

$size$ riêng ở mỗi tập hợp, vì nếu gọi thao tác

$std::size()$ thì sẽ sai vì nó sẽ bao gồm cả phần tử "đáng ra đã bị xóa" bị tính vào.

Code

void Paid() {
    while(!OweBig.empty() && OweBig.top() == Big.top()) 
        OweBig.pop(), Big.pop();

    while(!OweSmall.empty() && OweSmall.top() == Small.top()) 
        OweSmall.pop(), Small.pop();
}

void rev() {
    if(x == Small.top()) Small.pop(), sizSmall--;
    else if(x < Small.top()) OweSmall.push(x), sizSmall--;
    else if(x == Big.top()) Big.pop(), sizBig--;
    else if(x > Big.top()) OweBig.push(x), sizBig--;
    Paid();
    Balance();
}

2. Cải Tiến Xuất

• Một mẹo nhỏ khiến thời gian giảm đi đôi chút là ta sẽ lưu kết quả vào một mảng
  $ans$ trước rồi mới xuất ra.

Code

for(int i = 1 ; i <= q ; ++i) {
    cin >> c >> x;
    if(c == '+') add();
    else rev();
    ans[i] = Small.top();
}

for(int i = 1 ; i <= q ; ++i) cout << ans[i] << '\n';

Code Minh Họa

Time:

$O(n{\log }_{2}n)$
Space:

$O(n)$

CQTshadow Code

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;

const int N = 1e5 + 7;
const double eps = 1e-9;

template <typename X> using V = vector<X>;
template <typename X> 
    bool minimize(X &a, const X b) {
        if(a > b + eps) return a = b, 1;
        else return 0;
    }
template <typename X> 
    bool maximize(X &a, const X b) {
        if(a + eps < b) return a = b, 1;
        else return 0;
    }    

int q, sizSmall, sizBig, x;
char c;
priority_queue<int, V<int>, greater<int>> Big, OweBig;
priority_queue<int> Small, OweSmall;

void Paid() {
    while(!OweBig.empty() && OweBig.top() == Big.top()) 
        OweBig.pop(), Big.pop();

    while(!OweSmall.empty() && OweSmall.top() == Small.top()) 
        OweSmall.pop(), Small.pop();
}

void Balance() {
    if(sizSmall > sizBig + 1) {
        Big.push(Small.top()), sizBig++;
        Small.pop(), sizSmall--;
    }
    else if(sizSmall < sizBig) {
        Small.push(Big.top()), sizSmall++;
        Big.pop(), sizBig--;
    }
    Paid();
}

void add() {
    if(Small.empty()) Small.push(x), sizSmall++;
    else {
        int median = Small.top();
        if(x > median) Big.push(x), sizBig++;
        else Small.push(x), sizSmall++;
    }
    Balance();
}

void rev() {
    if(x == Small.top()) Small.pop(), sizSmall--;
    else if(x < Small.top()) OweSmall.push(x), sizSmall--;
    else if(x == Big.top()) Big.pop(), sizBig--;
    else if(x > Big.top()) OweBig.push(x), sizBig--;
    Paid();
    Balance();
}

int ans[1000002];

int main () {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> q;
    
    for(int i = 1 ; i <= q ; ++i) {
        cin >> c >> x;
        if(c == '+') add();
        else rev();
        ans[i] = Small.top();
    }

    for(int i = 1 ; i <= q ; ++i) cout << ans[i] << '\n';
}

SPyofgame Dynamic Median Template

/*
    @Author: SPyofgame
    @License: Free to use
    @Tag: Dynamic Median Data Structure
*/

#include <iostream>
#include <cassert>
#include <vector>
#include <queue>

using namespace std;

/// Data Structure that
/// - Insert element in O(log size)
/// - Erase element in O(log size)
/// - Find median in O(log size)
/// - Constant Factor: As high as C++std::priority_queue
template<typename T>
struct Dynamic_Median
{
    /// Diffrent Size | Expected Ratio: |L| >= |R| & |L| - |R| <= 1
    int diff = 0;

    /// Value can be duplicated

    /// Value Array
    priority_queue<T, vector<T>,   less<T>  > L;
    priority_queue<T, vector<T>, greater<T> > R;

    /// Erasing Queue
    priority_queue<T, vector<T>,   less<T>  > LEQ;
    priority_queue<T, vector<T>, greater<T> > REQ;

    /// Balance two array with expected ratio: |L| >= |R| & |L| - |R| <= 1      
    /// Return value: void
    /// Parameter: NULL
    /// Complexity: O(log size)
    /// Requirement: ALL OTHER FUNCTION use this on top
    /// Run-time-error: |L| = 0 or |R| = 0 while balancing
    ///                 Suspect (diff) behaved wrongly
    void balance()
    {
        if (diff > 1)
        {
            assert(L.size());
            R.push(L.top());
            L.pop();
            diff -= 2;
        }
        else if (diff < 0)
        {
            L.push(R.top());
            R.pop();
            diff += 2;
        }

        while (REQ.size() && REQ.top() == R.top()) REQ.pop(), R.pop();
        while (LEQ.size() && LEQ.top() == L.top()) LEQ.pop(), L.pop();
    }

    /// Find median of array S = (L + R)
    /// Return value: S[n / 2]       if n = |S| is even 
    ///               S[(n - 1) / 2] if n = |S| is odd
    ///
    /// Parameter: NULL
    /// Complexity: O(log size)
    /// Run-time-error: Balance() behaved wrongly
    ///                 |L| is empty after balancing
    T median()
    {
        balance();
        assert(L.size());
        return L.top();
    }

    /// Find median of array S = (L + R)
    /// Return value: S[n / 2]       if n = |S| is even 
    ///               S[(n + 1) / 2] if n = |S| is odd
    ///
    /// Parameter: NULL
    /// Complexity: O(log size)
    /// Run-time-error: Balance() behaved wrongly
    ///                 |R| is empty after balancing
    T median2()
    {
        balance();                
        assert(R.size());
        return R.top();
    }

    /// Insert (value) to array
    /// Return value: void
    /// Parameter: <T> value
    /// Complexity: O(log size)
    /// Run-time-error: Balance() behaved wrongly
    void insert(const T &value)
    {
        balance();
        if (L.empty() || value <= median()) 
            L.push(value), ++diff;
        else 
            R.push(value), --diff;
    }

    /// Erase (value) from array
    /// Return value: void
    /// Parameter: <T> value
    /// Complexity: O(log size)
    /// Run-time-error: Balance() behaved wrongly
    ///                 |L| = 0 or |R| = 0 while erasing
    void erase(const T &value)
    {
        balance();
        if (value <= median()) /// If median() cost is high
        {                      /// Then please precalculate it
            --diff;
            (value == median()) ? L.pop() : LEQ.push(value);
        }
        else
        {
            ++diff;
            (value == median2()) ? R.pop() : REQ.push(value);
        }
    }
};

int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);
    
    int q;
    cin >> q;

    Dynamic_Median<int> S;
    while (q-->0)
    {
        char operation;
        cin >> operation;

        int value;
        cin >> value;
        
        if (operation == '+') 
            S.insert(value);
        else 
            S.erase(value);

        cout << S.median() << "\n";
    }

    return 0;
}