イベントソート

published: 2021/10/1 update: 2021/10/1

Table of Contents

概要

半開区間の集合が与えられます。区間ごとに値が与えられているとします。これらの区間は重なっていることもあります。

このとき、以下のクエリが与えられます。 地点の位置に定義されているの最小値(または最大値)を答えてください。

考え方

ABC128-Eの例を考えます。

abc128_example

図としてはこのようになっており、それぞれのクエリの最小値を求める必要があります。 このとき、についての集合を考えます。そして、左端の部分をへの挿入、右端の部分をからの削除というイベントとしてとらえます。また、クエリはクエリというイベントとして処理してみます。

このとき、

  1. 挿入イベント
  2. 削除イベント
  3. クエリイベント

というイベントがあることになります。これらのイベントを場所順に処理していきます。挿入イベントと削除イベントは順不同ですが、クエリイベントは同じ場所の挿入・削除終了後に処理される必要があります。

ABC128の例を処理してみると以下のようになることがわかります。

こうすると、場所における範囲の持つ値は、集合に入っている値になります。なので、クエリイベントでは、集合の最小値がその場所における答え、ということになります。Indexを用意しておくと、答えの配列に直接最小値を書き込めます。

上の例では複数回同じ値が集合に挿入されませんでしたが、実際には複数回の挿入があり得ます。そこで、集合を扱うためのデータ構造としては、multisetを使う必要があります。

実装 in Rust

multiset

Rustではmultisetはないので自分で実装する必要があるようです。

BtreeMapを使えば比較的簡単に順序付きmultisetもどきを実装できます。keyとして集合として扱いたい値を持ち、valueとしてカウントを持ちます。カウントが0になれば、keyを削除します。

use std::collections::BTreeMap;

/// Ordered MultiSet
#[derive(Debug, Clone)]
pub struct BMultiSet<T> {
    pub inner_map: BTreeMap<T, usize>,
}

impl<T: Ord> BMultiSet<T> {
    pub fn new() -> Self {
        Self {
            inner_map: BTreeMap::new(),
        }
    }

    /// Insert Value
    pub fn insert(&mut self, x: T) {
        *self.inner_map.entry(x).or_insert(0) += 1;
    }

    /// Decrement count of the value.  
    /// If count is zero, remove this value.
    pub fn erase_one(&mut self, x: T) -> Option<T> {
        if let Some(count) = self.inner_map.get_mut(&x) {
            *count -= 1;
            if *count == 0 {
                self.inner_map.remove(&x);
            }
            Some(x)
        } else {
            None
        }
    }

    /// Return count of value
    pub fn count(&self, x: &T) -> Option<&usize> {
        self.inner_map.get(x)
    }

    /// Remove value regradless of count
    pub fn erase_all(&mut self, x: T) -> Option<T> {
        self.inner_map.remove(&x);
        Some(x)
    }

    pub fn min(&self) -> Option<&T> {
        self.inner_map.iter().nth(0).map(|x| x.0)
    }

    pub fn max(&self) -> Option<&T> {
        self.inner_map.iter().last().map(|x| x.0)
    }

    pub fn is_empty(&self) -> bool {
        self.inner_map.is_empty()
    }
}

enumにおけるPartialOrd

Actionenumとして定義できると嬉しいです。RustのenumにPartialOrdderiveすると、上から順番に大きいと判断されます。

#[derive(Debug, PartialEq, PartialOrd)]
enum Action {
    Insert,
    Delete,
    Query,
}

#[test]
fn test_partialeq() {
    assert!(Action::Insert > Action::Query);
    assert!(Action::Delete > Action::Query);
}

記事に間違い等ありましたら、お気軽に以下までご連絡ください

E-mail: illumination.k.27|gmail.com ("|" replaced to "@")

Twitter: @illuminationK

当HPを応援してくれる方は下のリンクからお布施をいただけると非常に励みになります。

Ofuse

Other Articles

Site Map

Table of Contents

    概要

    考え方

    実装 in Rust

      multiset

      enumにおけるPartialOrd


当HPを応援してくれる方は下のリンクからお布施をいただけると非常に励みになります。

Ofuse
Privacy Policy

Copyright © illumination-k 2020-2021.