ランレングス圧縮 (Run Length Encoding)
- Run(seq): 列 seq をランレングス圧縮する
戻り値 struct RLE_RES
- cnt: 連続部分列集合の個数
- x: 部分列の要素
- size: 部分列の長さ
- sub: 部分列集合
- range: 部分列と対応する列の半開区間 (0-index)
#include <bits/stdc++.h> namespace NyaaLIB { /** * ランレングス圧縮ライブラリ O(N) **/ template <class T> struct RLE_RES { long long cnt = 0; std::vector<T> x; std::vector<long long> size; std::vector<std::vector<T>> sub; std::vector<std::pair<long long, long long>> range; }; template <class T> struct DS_RLE { // Run Length Encoding using ll = long long; RLE_RES<T> Run(vector<T>& seq) { RLE_RES<T> res; res.range.push_back({ 0,0 }); for (ll i = 1; i < ll(seq.size()); i++) { if (seq[i - 1] != seq[i]) { AddSub(seq, res.range.back().first, i, res); res.range.push_back({ i,0 }); } } AddSub(seq, res.range.back().first, ll(seq.size()), res); res.cnt = ll(res.x.size()); return res; } private: void AddSub(std::vector<T>& seq, ll l, ll r, RLE_RES<T>& res) { res.x.push_back(seq[l]); res.size.push_back(r - res.range.back().first); res.sub.resize(res.sub.size() + 1); for (ll j = res.range.back().first; j < r; j++) res.sub.back().push_back(seq[l]); res.range.back().second = r; } }; }
