NyaaLIB::DS_RLE

ランレングス圧縮 (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;
		}
	};
}

実装例
https://atcoder.jp/contests/arc007/submissions/31406997