verify/standalone-dynamic-median.test.cpp

• View this file on GitHub
• Last update: 2026-05-29 20:48:10+09:00

Depends on

• 値の追加・削除と中央値取得 (structure/others/dynamic-median.hpp)

Code

// competitive-verifier: STANDALONE

#include <algorithm>
#include <cassert>
#include <limits>
#include <vector>

#include "../structure/others/dynamic-median.hpp"

namespace {
template <class T> std::vector<T> sorted_values(std::vector<T> values) {
    std::sort(values.begin(), values.end());
    return values;
}

template <class T>
void check_dynamic_median(const DynamicMedian<T> &median,
                          const std::vector<T> &values) {
    assert(!values.empty());
    const auto sorted = sorted_values(values);
    assert(median.median(DynamicMedianMode::Lower) ==
           sorted[(sorted.size() - 1) / 2]);
    assert(median.median() == sorted[(sorted.size() - 1) / 2]);
    assert(median.median(DynamicMedianMode::Upper) ==
           sorted[sorted.size() / 2]);
    const long double expected_average =
        (static_cast<long double>(sorted[(sorted.size() - 1) / 2]) +
         static_cast<long double>(sorted[sorted.size() / 2])) /
        2.0L;
    assert(median.template median<long double>(DynamicMedianMode::Average) ==
           expected_average);
}

void check_scripted_operations() {
    DynamicMedian<int> median;
    std::vector<int> values;

    const std::vector<int> additions{5, -1, 5, -3, 7, 0, 0, 12, -8};
    for (int value : additions) {
        median.add(value);
        values.push_back(value);
        check_dynamic_median(median, values);
    }

    const std::vector<int> erasures{4, 5, -1, 0, 0, 12, -8, -3, 5, 7};
    for (int value : erasures) {
        const auto it = std::find(values.begin(), values.end(), value);
        const bool expected = it != values.end();
        assert(median.erase(value) == expected);
        if (expected) {
            values.erase(it);
            if (!values.empty()) {
                check_dynamic_median(median, values);
            }
        }
    }
}

void check_known_cases() {
    DynamicMedian<long long> median;
    assert(!median.erase(0));
    median.add(4);
    assert(median.median() == 4);
    assert(median.median(DynamicMedianMode::Upper) == 4);
    assert(median.median<long double>(DynamicMedianMode::Average) == 4.0L);

    median.add(1);
    assert(median.median(DynamicMedianMode::Lower) == 1);
    assert(median.median(DynamicMedianMode::Upper) == 4);
    assert(median.median<long double>(DynamicMedianMode::Average) == 2.5L);

    median.add(1);
    assert(median.median(DynamicMedianMode::Lower) == 1);
    assert(median.median(DynamicMedianMode::Upper) == 1);
    assert(median.median<long double>(DynamicMedianMode::Average) == 1.0L);

    assert(median.erase(1));
    assert(median.median(DynamicMedianMode::Lower) == 1);
    assert(median.median(DynamicMedianMode::Upper) == 4);
    assert(median.median<long double>(DynamicMedianMode::Average) == 2.5L);

    DynamicMedian<long long> large_median;
    const long long max_value = std::numeric_limits<long long>::max();
    large_median.add(max_value - 1);
    large_median.add(max_value);
    assert(large_median.median(DynamicMedianMode::Average) == max_value - 1);

    DynamicMedian<long long> signed_median;
    const long long min_value = std::numeric_limits<long long>::lowest();
    signed_median.add(min_value);
    signed_median.add(max_value);
    assert(signed_median.median(DynamicMedianMode::Average) == 0);
}

void self_test() {
    check_known_cases();
    check_scripted_operations();
}
} // namespace

int main() {
    self_test();
    return 0;
}

#line 1 "verify/standalone-dynamic-median.test.cpp"
// competitive-verifier: STANDALONE

#include <algorithm>
#include <cassert>
#include <limits>
#include <vector>

#line 1 "structure/others/dynamic-median.hpp"



// 値の多重集合に対して追加、削除、中央値取得を行う。
// 中央値は下側、上側、両側の算術平均から選べる。
// T はコピー可能で、std::multiset で扱える比較を持つ型を仮定する。
// median は空でないことを仮定する。
// add, erase は O(log N)、median は O(1) である。

#line 11 "structure/others/dynamic-median.hpp"
#include <set>
#include <type_traits>

enum class DynamicMedianMode { Lower, Upper, Average };

template <class T> struct DynamicMedian {
    std::multiset<T> lower_values;
    std::multiset<T> upper_values;

    void add(T x) {
        if (lower_values.empty() || !(*lower_values.rbegin() < x)) {
            lower_values.insert(x);
        } else {
            upper_values.insert(x);
        }
        balance();
    }

    bool erase(T x) {
        auto lower_itr = lower_values.find(x);
        if (lower_itr != lower_values.end()) {
            lower_values.erase(lower_itr);
            balance();
            return true;
        }

        auto upper_itr = upper_values.find(x);
        if (upper_itr != upper_values.end()) {
            upper_values.erase(upper_itr);
            balance();
            return true;
        }

        return false;
    }

    template <class Result = T>
    Result median(DynamicMedianMode mode = DynamicMedianMode::Lower) const {
        assert(!lower_values.empty());
        const T &lower_median = *lower_values.rbegin();

        if (mode == DynamicMedianMode::Lower) {
            return static_cast<Result>(lower_median);
        }
        if (lower_values.size() != upper_values.size()) {
            return static_cast<Result>(lower_median);
        }

        const T &upper_median = *upper_values.begin();
        if (mode == DynamicMedianMode::Upper) {
            return static_cast<Result>(upper_median);
        }

        assert(mode == DynamicMedianMode::Average);
        const Result lower = static_cast<Result>(lower_median);
        const Result upper = static_cast<Result>(upper_median);
        if constexpr (std::is_integral_v<Result>) {
            if constexpr (std::is_signed_v<Result>) {
                if (lower < 0 && 0 < upper) {
                    return (lower + upper) / 2;
                }
            }
            return lower / 2 + upper / 2 + (lower % 2 + upper % 2) / 2;
        } else if constexpr (requires(Result lhs, Result rhs) {
                                 (lhs + rhs) / Result(2);
                             }) {
            return (lower + upper) / Result(2);
        } else {
            assert(false);
            return static_cast<Result>(lower_median);
        }
    }

  private:
    void balance() {
        while (lower_values.size() < upper_values.size()) {
            lower_values.insert(*upper_values.begin());
            upper_values.erase(upper_values.begin());
        }
        while (lower_values.size() > upper_values.size() + 1) {
            auto itr = lower_values.end();
            --itr;
            upper_values.insert(*itr);
            lower_values.erase(itr);
        }
    }
};


#line 9 "verify/standalone-dynamic-median.test.cpp"

namespace {
template <class T> std::vector<T> sorted_values(std::vector<T> values) {
    std::sort(values.begin(), values.end());
    return values;
}

template <class T>
void check_dynamic_median(const DynamicMedian<T> &median,
                          const std::vector<T> &values) {
    assert(!values.empty());
    const auto sorted = sorted_values(values);
    assert(median.median(DynamicMedianMode::Lower) ==
           sorted[(sorted.size() - 1) / 2]);
    assert(median.median() == sorted[(sorted.size() - 1) / 2]);
    assert(median.median(DynamicMedianMode::Upper) ==
           sorted[sorted.size() / 2]);
    const long double expected_average =
        (static_cast<long double>(sorted[(sorted.size() - 1) / 2]) +
         static_cast<long double>(sorted[sorted.size() / 2])) /
        2.0L;
    assert(median.template median<long double>(DynamicMedianMode::Average) ==
           expected_average);
}

void check_scripted_operations() {
    DynamicMedian<int> median;
    std::vector<int> values;

    const std::vector<int> additions{5, -1, 5, -3, 7, 0, 0, 12, -8};
    for (int value : additions) {
        median.add(value);
        values.push_back(value);
        check_dynamic_median(median, values);
    }

    const std::vector<int> erasures{4, 5, -1, 0, 0, 12, -8, -3, 5, 7};
    for (int value : erasures) {
        const auto it = std::find(values.begin(), values.end(), value);
        const bool expected = it != values.end();
        assert(median.erase(value) == expected);
        if (expected) {
            values.erase(it);
            if (!values.empty()) {
                check_dynamic_median(median, values);
            }
        }
    }
}

void check_known_cases() {
    DynamicMedian<long long> median;
    assert(!median.erase(0));
    median.add(4);
    assert(median.median() == 4);
    assert(median.median(DynamicMedianMode::Upper) == 4);
    assert(median.median<long double>(DynamicMedianMode::Average) == 4.0L);

    median.add(1);
    assert(median.median(DynamicMedianMode::Lower) == 1);
    assert(median.median(DynamicMedianMode::Upper) == 4);
    assert(median.median<long double>(DynamicMedianMode::Average) == 2.5L);

    median.add(1);
    assert(median.median(DynamicMedianMode::Lower) == 1);
    assert(median.median(DynamicMedianMode::Upper) == 1);
    assert(median.median<long double>(DynamicMedianMode::Average) == 1.0L);

    assert(median.erase(1));
    assert(median.median(DynamicMedianMode::Lower) == 1);
    assert(median.median(DynamicMedianMode::Upper) == 4);
    assert(median.median<long double>(DynamicMedianMode::Average) == 2.5L);

    DynamicMedian<long long> large_median;
    const long long max_value = std::numeric_limits<long long>::max();
    large_median.add(max_value - 1);
    large_median.add(max_value);
    assert(large_median.median(DynamicMedianMode::Average) == max_value - 1);

    DynamicMedian<long long> signed_median;
    const long long min_value = std::numeric_limits<long long>::lowest();
    signed_median.add(min_value);
    signed_median.add(max_value);
    assert(signed_median.median(DynamicMedianMode::Average) == 0);
}

void self_test() {
    check_known_cases();
    check_scripted_operations();
}
} // namespace

int main() {
    self_test();
    return 0;
}

Back to top page