連長圧縮
(Src/Sequence/RunLengthEncoding.hpp)

• View this file on GitHub
• Last update: 2023-07-29 13:13:36+09:00
• Include: #include "Src/Sequence/RunLengthEncoding.hpp"

概要

長さ $N$ の列 $A$ を連長圧縮して、各要素を管理します。また、先頭と末尾に限り要素の追加、削除に対応しています。

与えられた列の連続した要素を (要素、連続している数) のペアの列で表現することを連長圧縮といいます。

例えば、 $A = (1, 1, 2, 3, 3, 3, 4, 1, 1)$ を連長圧縮した列は $((1, 2), (2, 1), (3, 3), (4, 1), (1, 2))$ です。

以後、入力の列を $A$ 、連長圧縮後の列を $B$ とします。

使い方

テンプレート引数

template <class Value, class Number = u64>

$A$ の要素の型をValueに指定します。 「連続している数」の型をNumberに指定します。Numberはデフォルトでzawa::u64 = std::uint64_tが指定されています。

コンストラクタ

(1) RunLengthEncoding() = default;
(2) RunLengthEncoding<InputIterator>(InputIterator first, InputIterator last)
(3) RunLengthEncoding(const std::vector<Value>& a)

(1) デフォルトコンストラクタ: 空列で $B$ を構築する

計算量: 定数時間

(2) イテレータ範囲コンストラクタ: [first, last)の範囲を要素として $B$ を構築する

• std::string等に対してはこのコンストラクタを使用してください

計算量: firstからlastの距離に対して線形時間

(3) Aから $B$ を構築する

計算量: $O(\mid A \mid)$

size

constexpr usize size() const noexcept

$\mid B\mid$ を返します。

計算量: 定数時間

sum

constexpr u64 sum() const noexcept

$\mid A\mid$ を返します。

計算量: 定数時間

operator[]

const Data& operator[](u32 i) const noexcept

$B_{i}$ を返します。 Dataは以下のようなクラスです。

class Data {
private:
    Value value_;
    Number number_;
public:
    const Value& value() const noexcept // 要素の値
    Number number() const noexcept // 連続している数
};

制約: $0\ \le\ i\ \le\ \mid B\mid$

計算量: 定数時間

value

const Value& value(u32 i) const noexcept

$B_i$ の保管している要素を返します。

制約: $0\ \le\ i\ \le\ \mid B\mid$

計算量: 定数時間

number

const Number number(u32 i) const noexcept {

$B_i$ の連続している数を返します。

制約: $0\ \le\ i\ \le\ \mid B\mid$

計算量: 定数時間

begin

typename decltype(seq_)::const_iterator begin() const noexcept

$B$ の先頭要素のconst_iteratorを返します。(要素の変更を想定していないため、constでないイテレータは提供していません)

計算量: 定数時間

end

typename decltype(seq_)::const_iterator end() const noexcept

$B$ の末尾の次の要素のconst_iteratorを返します。(要素の変更を想定していないため、constでないイテレータは提供していません)

計算量: 定数時間

pushBack

void pushBack(const Value& value, const Number number = Number{1})

$A$ の末尾にvalueをnumber個挿入します。応じて $B$ も変更されます。

• numberはデフォルトで $1$ になっています。

計算量: 定数時間

pushFront

void pushFront(const Value& value, const Number number = Number{1}) {

$A$ の末尾にvalueをnumber個挿入します。応じて $B$ も変更されます。

• numberはデフォルトで $1$ になっています。

計算量: 定数時間

popBack

(1) void popBack()
(2) std::vector<Data> popBack(u64 number)

(1) $B$ の末尾要素を除去する。 $A$ も応じて変更される (先頭から末尾要素を連続している分除去する)

制約: $B$ が非空であること

計算量: 定数時間

(2) $A$ を末尾からnumber要素除去する。除去した要素を連長圧縮したvectorを返す。

• $B$ も応じて変更される

制約: $\text{number}\ \le\ \mid A\mid$

計算量: $O(\mid B\mid)$

• pushBackやpushFrontを呼ば出さない場合、(2)popFront(2)popBackを呼び出した全体の計算時間の実行限界が $O(\mid B\mid)$ に抑えられます。

popFront

(1) void popFront()
(2) std::vector<Data> popFront(u64 number)

(1) $B$ の先頭要素を除去する。 $A$ も応じて変更される (先頭から先頭要素を連続している分除去する)

制約: $B$ が非空であること

計算量: 定数時間

(2) $A$ を先頭からnumber要素除去する。除去した要素を連長圧縮したvectorを返す。

• $B$ も応じて変更される

制約: $\text{number}\ \le\ \mid A\mid$

計算量: $O(\mid B\mid)$

• pushBackやpushFrontを呼ば出さない場合、(2)popFront(2)popBackを呼び出した全体の計算時間の実行限界が $O(\mid B\mid)$ に抑えられます。

アルゴリズム

よしなにやっています。 $B$ をstd::dequeで持つことでpushHoge popHogeに対応しています。

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/AtCoder/abc247_d.test.cpp
• Test/AtCoder/abc299_c.test.cpp
• Test/AtCoder/abc311_b.test.cpp
• Test/Manual/agc026_a.test.cpp

Code

#pragma once

#include "../Template/TypeAlias.hpp"

#include <deque>
#include <vector>
#include <cassert>

namespace zawa {

template <class Value, class Number = u64>
class RunLengthEncoding {
public:
    class Data {
    private:
        Value value_;
        Number number_;
    public:
        Data() = default;
        Data(const Value& value, Number number) : value_{ value }, number_{ number } {}

        const Value& value() const noexcept {
            return value_;
        }

        Number number() const noexcept {
            return number_;
        }

        friend RunLengthEncoding;
    };

private:
    std::deque<Data> seq_;
    u64 sum_{};

    template <class InputIterator>
    inline void build(InputIterator first, InputIterator last) {
        for (auto it{ first } ; it != last ; it++) {
            if (seq_.empty() or seq_.back().value() != *it) {
                seq_.emplace_back(*it, Number{1});
            }
            else {
                seq_.back().number_++;
            }
            sum_++;
        }
    }

public:
    RunLengthEncoding() = default;

    template <class InputIterator>
    RunLengthEncoding(InputIterator first, InputIterator last) {
        build(first, last);
    }

    RunLengthEncoding(const std::vector<Value>& a) {
        build(a.begin(), a.end());
    }

    constexpr usize size() const noexcept {
        return seq_.size();
    }

    constexpr u64 sum() const noexcept {
        return sum_;
    }

    const Data& operator[](u32 i) const noexcept {
        assert(i < size());
        return seq_[i];
    }

    const Value& value(u32 i) const noexcept {
        assert(i < size());
        return seq_[i].value();
    }

    const Number number(u32 i) const noexcept {
        assert(i < size());
        return seq_[i].number();
    }

    typename decltype(seq_)::const_iterator begin() const noexcept {
        return seq_.begin();
    }

    typename decltype(seq_)::const_iterator end() const noexcept {
        return seq_.end();
    }

    const Data& front() const noexcept {
        assert(size());
        return seq_.front();
    }

    const Data& back() const noexcept {
        assert(size());
        return seq_.back();
    }

    void pushBack(const Value& value, const Number number = Number{1}) {
        sum_ += number;
        if (seq_.empty() or seq_.back().value() != value) {
            seq_.emplace_back(value, number);
        }
        else {
            seq_.back().number_ += number;
        }
    }

    void pushFront(const Value& value, const Number number = Number{1}) {
        sum_ += number;
        if (seq_.empty() or seq_.front().value() != value) {
            seq_.emplace_front(value, number);
        }
        else {
            seq_.front().number_ += number;
        }
    }

    void popBack() {
        assert(size());
        sum_ -= seq_.back().number();
        seq_.pop_back();
    }

    void popFront() {
        assert(size());
        sum_ -= seq_.front().number();
        seq_.pop_front();
    }

    std::vector<Data> popBack(u64 number) {
        assert(number <= sum());
        sum_ -= number;
        std::vector<Data> res;
        while (number and number >= seq_.back().number()) {
            res.push_back(seq_.back());
            number -= seq_.back().number();
            seq_.pop_back();
        }
        if (number) {
            res.emplace_back(seq_.back().value(), number);
            seq_.back().number_ -= number;
        }
        return res;
    }

    std::vector<Data> popFront(u64 number) {
        assert(number <= sum());
        sum_ -= number;
        std::vector<Data> res;
        while (number and number >= seq_.front().number()) {
            res.push_back(seq_.front());
            number -= seq_.front().number();
            seq_.pop_front();
        }
        if (number) {
            res.emplace_back(seq_.front().value(), number);
            seq_.front().number_ -= number;
        }
        return res;
    }
};

} // namespace zawa

#line 2 "Src/Sequence/RunLengthEncoding.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Sequence/RunLengthEncoding.hpp"

#include <deque>
#include <vector>
#include <cassert>

namespace zawa {

template <class Value, class Number = u64>
class RunLengthEncoding {
public:
    class Data {
    private:
        Value value_;
        Number number_;
    public:
        Data() = default;
        Data(const Value& value, Number number) : value_{ value }, number_{ number } {}

        const Value& value() const noexcept {
            return value_;
        }

        Number number() const noexcept {
            return number_;
        }

        friend RunLengthEncoding;
    };

private:
    std::deque<Data> seq_;
    u64 sum_{};

    template <class InputIterator>
    inline void build(InputIterator first, InputIterator last) {
        for (auto it{ first } ; it != last ; it++) {
            if (seq_.empty() or seq_.back().value() != *it) {
                seq_.emplace_back(*it, Number{1});
            }
            else {
                seq_.back().number_++;
            }
            sum_++;
        }
    }

public:
    RunLengthEncoding() = default;

    template <class InputIterator>
    RunLengthEncoding(InputIterator first, InputIterator last) {
        build(first, last);
    }

    RunLengthEncoding(const std::vector<Value>& a) {
        build(a.begin(), a.end());
    }

    constexpr usize size() const noexcept {
        return seq_.size();
    }

    constexpr u64 sum() const noexcept {
        return sum_;
    }

    const Data& operator[](u32 i) const noexcept {
        assert(i < size());
        return seq_[i];
    }

    const Value& value(u32 i) const noexcept {
        assert(i < size());
        return seq_[i].value();
    }

    const Number number(u32 i) const noexcept {
        assert(i < size());
        return seq_[i].number();
    }

    typename decltype(seq_)::const_iterator begin() const noexcept {
        return seq_.begin();
    }

    typename decltype(seq_)::const_iterator end() const noexcept {
        return seq_.end();
    }

    const Data& front() const noexcept {
        assert(size());
        return seq_.front();
    }

    const Data& back() const noexcept {
        assert(size());
        return seq_.back();
    }

    void pushBack(const Value& value, const Number number = Number{1}) {
        sum_ += number;
        if (seq_.empty() or seq_.back().value() != value) {
            seq_.emplace_back(value, number);
        }
        else {
            seq_.back().number_ += number;
        }
    }

    void pushFront(const Value& value, const Number number = Number{1}) {
        sum_ += number;
        if (seq_.empty() or seq_.front().value() != value) {
            seq_.emplace_front(value, number);
        }
        else {
            seq_.front().number_ += number;
        }
    }

    void popBack() {
        assert(size());
        sum_ -= seq_.back().number();
        seq_.pop_back();
    }

    void popFront() {
        assert(size());
        sum_ -= seq_.front().number();
        seq_.pop_front();
    }

    std::vector<Data> popBack(u64 number) {
        assert(number <= sum());
        sum_ -= number;
        std::vector<Data> res;
        while (number and number >= seq_.back().number()) {
            res.push_back(seq_.back());
            number -= seq_.back().number();
            seq_.pop_back();
        }
        if (number) {
            res.emplace_back(seq_.back().value(), number);
            seq_.back().number_ -= number;
        }
        return res;
    }

    std::vector<Data> popFront(u64 number) {
        assert(number <= sum());
        sum_ -= number;
        std::vector<Data> res;
        while (number and number >= seq_.front().number()) {
            res.push_back(seq_.front());
            number -= seq_.front().number();
            seq_.pop_front();
        }
        if (number) {
            res.emplace_back(seq_.front().value(), number);
            seq_.front().number_ -= number;
        }
        return res;
    }
};

} // namespace zawa

Back to top page