SortedSet
(src/data_structure/sorted_set.hpp)

• View this file on GitHub
• Last update: 2024-11-09 01:34:39+09:00
• Include: #include "src/data_structure/sorted_set.hpp"

SortedSet

• 要素の挿入・削除
• 要素の検索
• 要素の個数の取得
• $k$ 番目に小さい値の取得
• $x$ 以上の最小値の取得

を $O(\log n)$ 時間で処理できます．

コンストラクタ

(1) SortedSet st
(2) SortedMultiSet mst

• (1): 空の平衡二分探索木 st を構築します．
• (2): 要素の重複をゆるした空の平衡二分探索木 mst を構築します．

計算量

• $O(1)$

insert

(1) pair<iterator, bool> st.insert(int x)
(2) pair<iterator, bool> mst.insert(int x)

st および mst に要素 $x$ を追加します．
st にすでに $x$ が入っている場合は何もしません．

返り値として，イテレータと挿入が成功したかを示すフラグが得られます．

計算量

• $O(\log n)$

erase

(1) pair<iterator, bool> st.erase(int x)
(2) pair<iterator, bool> mst.erase(st.find_by_order(st.order_of_key(6)))

st および mst から要素 $x$ を削除します．
すでに $x$ が入っていない場合は何もしません．
mst に複数の $x$ が入っている場合，要素は $1$ つだけ削除されます．

返り値として，イテレータと削除が成功したかを示すフラグが得られます．

計算量

• $O(\log n)$

find

(1) iterator st.find(int x)
(2) iterator mst.find(int x)

要素 $x$ のイテレータを返します．
要素がない場合，st.end() および mst.end() を返します．

計算量

• $O(\log n)$

size

(1) int st.size()
(2) int mst.size()

st や mst の中に入っている要素の個数を返します．

計算量

• $O(1)$

find_by_order

(1) iterator st.find_by_order(int k)
(2) iterator mst.find_by_order(int k)

$k$ 番目に小さい値のイテレータを返します．

計算量

• $O(\log n)$

order_of_key

(1) int st.order_of_key(int x)
(2) int mst.order_of_key(int x)

$x$ 以上の最小値が何番目に小さいかを返します．

計算量

• $O(\log n)$

Depends on

• policy_based_data_structure (src/template/policy_based_data_structure.hpp)
• template (src/template/template.hpp)

Verified with

• verify/yukicoder/649.test.cpp

Code

#pragma once
#include "../template/template.hpp"
#include "../template/policy_based_data_structure.hpp"
using SortedSet = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
using SortedMultiSet = tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>;

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 2 "src/template/policy_based_data_structure.hpp"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
#line 4 "src/data_structure/sorted_set.hpp"
using SortedSet = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
using SortedMultiSet = tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>;

Back to top page