---
tags: VNOJ, Template, Data Structure, CQTshadow, SPyofgame
title: 🌱 Dynamic Median
author: Editorial-Slayers Team
license: Public domain
---

<style>
.markdown-body { max-width: 2048px; }
h1 {
color: blue;
font-family: verdana;
font-size: 500%;
}
h2 {
color: red;
font-family: verdana;
font-size: 400%;
}
h3 {
color: gray;
font-size: 300%;
font-family : verdana;
}
h4 {
font-family : verdana;
font-size: 200%;
}
</style>

$\Huge \text{🌱 Dynamic Median}$

-----

###### 🔗 Link: [https://oj.vnoi.info/problem/medquery](https://oj.vnoi.info/problem/medquery)
###### 📌 Tags: `Template`, `Data Structure`
###### 👤 Writter: @CQTshadow
###### 👥 Contributor: @SPyofgame
###### 📋 Content:

[TOC]

-----
# 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 $\left[1, \left \lfloor\frac{k + 1}{2}\right \rfloor\right]$
- Tập hợp $Big$ : Lưu trữ các phần tử có vị trí thuộc khoảng $\left[\left \lfloor\frac{k + 1}{2}\right \rfloor + 1, k\right]$

$\Longrightarrow$ Để duy trì như yêu cầu, ta chỉ cần đảm bảo $0 \leq Small_{size} - Big_{size} \leq 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** : $Small_{size} > Big_{size} + 1$
$\Longrightarrow$ 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** : $Small_{size} < Big_{size}$
$\Longrightarrow$ 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.
:::success
:::spoiler 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$
$\Longrightarrow$ Ta thêm nó vào tập hợp $Big$.
- Ngược lại
$\Longrightarrow$ 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**
:::success
:::spoiler 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 $\Longrightarrow$ **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(log_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.**
:::success
:::spoiler 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.
:::success
:::spoiler 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)$ 
> [color=lightgreen]

:::success
:::spoiler 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';
}

:::


:::success
:::spoiler 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;
}

:::