隣接差集合
(DataStructure/AdjacentDiffSet.hpp)

• View this file on GitHub
• Last update: 2024-05-06 12:56:26+09:00
• Include: #include "DataStructure/AdjacentDiffSet.hpp"

概要

追加した要素からなる集合をソートした際に隣接差の最大値、最小値を得るためのライブラリ。
ここらへんの問題殴る用のライブラリ。

• AtCoder Beginner Contest 308「G - Minimum Xor Pair Query」
• Codeforces Round 894 (Div. 3)「G. The Great Equalizer」

関数名など	機能	計算量
Adjacent_Diff_Set	空集合を作成。要素の集合には番兵が入れられる。	$\text{O}(1)$
void add(long long v)	要素 $v$ を追加する。	$\text{O}(\log N)$
void del(long long v)	要素 $v$ を削除する。	$\text{O}(\log N)$
long long max()	加えられた要素の最大値を取得。	$\text{O}(\log N)$
long long min()	加えられた要素の最小値を取得。	$\text{O}(\log N)$
long long max_diff()	加えられた要素をソートしたときの隣接差の最大値を取得。 要素数が2未満の場合は 0 を返す。	$\text{O}(\log N)$
long long min_diff()	加えられた要素をソートしたときの隣接差の最小値を取得。 要素数が2未満の場合は 0 を返す。	$\text{O}(\log N)$

Code

struct Adjacent_Diff_Set {
    const long long inf = 1ll << 60;
    std::multiset<long long> S, D;
    Adjacent_Diff_Set(){
        S.insert(-inf);
        S.insert(inf);
    }
    void add(long long v){
        auto ba_itr = S.lower_bound(v);
        auto fr_itr = std::prev(ba_itr);
        if(*ba_itr != inf && *fr_itr != -inf){
            D.erase(D.find(*ba_itr - *fr_itr));
        }
        if(*ba_itr != inf) D.insert(*ba_itr - v);
        if(*fr_itr != -inf) D.insert(v - *fr_itr);
        S.insert(v);
    }
    void del(long long v){
        auto it = S.lower_bound(v);
        auto ba_itr = std::next(it);
        auto fr_itr = std::prev(it);
        if(*ba_itr != inf) D.erase(D.find(*ba_itr - v));
        if(*fr_itr != -inf) D.erase(D.find(v - *fr_itr));
        if(*ba_itr != inf && *fr_itr != -inf){
            D.insert(*ba_itr - *fr_itr);
        }
        S.erase(it);
    }
    long long max(){ return *std::next(S.rbegin()); }
    long long min(){ return *std::next(S.begin()); }
    long long max_diff(){ return D.empty() ? 0 : *D.rbegin(); }
    long long min_diff(){ return D.empty() ? 0 : *D.begin(); }
};

#line 1 "DataStructure/AdjacentDiffSet.hpp"
struct Adjacent_Diff_Set {
    const long long inf = 1ll << 60;
    std::multiset<long long> S, D;
    Adjacent_Diff_Set(){
        S.insert(-inf);
        S.insert(inf);
    }
    void add(long long v){
        auto ba_itr = S.lower_bound(v);
        auto fr_itr = std::prev(ba_itr);
        if(*ba_itr != inf && *fr_itr != -inf){
            D.erase(D.find(*ba_itr - *fr_itr));
        }
        if(*ba_itr != inf) D.insert(*ba_itr - v);
        if(*fr_itr != -inf) D.insert(v - *fr_itr);
        S.insert(v);
    }
    void del(long long v){
        auto it = S.lower_bound(v);
        auto ba_itr = std::next(it);
        auto fr_itr = std::prev(it);
        if(*ba_itr != inf) D.erase(D.find(*ba_itr - v));
        if(*fr_itr != -inf) D.erase(D.find(v - *fr_itr));
        if(*ba_itr != inf && *fr_itr != -inf){
            D.insert(*ba_itr - *fr_itr);
        }
        S.erase(it);
    }
    long long max(){ return *std::next(S.rbegin()); }
    long long min(){ return *std::next(S.begin()); }
    long long max_diff(){ return D.empty() ? 0 : *D.rbegin(); }
    long long min_diff(){ return D.empty() ? 0 : *D.begin(); }
};

Back to top page