7K12 blog

猫でも分かるアルゴリズム解説

NyaaLIB_XXL (XXライブラリまとめ)

尺取法 (Two Pointers)

探索列から条件を満たす部分列を求める 計算量  O(N)
利便性のため内部で {index, element} のペアに変換している

参考 https://qiita.com/keroru/items/6e0a22e8c9bf2a24dc68

  • 右手と左手について

右手は auto& [ri, re] = psub.back();
左手は auto& [li, le] = psub.front();
のように書けば右手や左手の情報 {index, element} を取得できる

  • auto ng = [&]() について

満たさない条件を書いて bool 型で返す
return !(満たす条件); で返すようにすると分かりやすい

#include <bits/stdc++.h>

namespace NyaaLIB_XXL
{
	namespace TwoPointers
	{
		using ll = long long;
		auto tp = [&](auto& seq) -> void
		{	// 探索対象を入力、内部で {index, element} のペアに変換しておく
			using T = long long; // 要素の型
			std::deque<std::pair<ll, T>> pseq, psub; // pseq は探索列 psub は部分列
			for (ll i = 0; i < (ll)seq.size(); i++) pseq.push_back({ i, seq[i] });

			for (auto& e : pseq)
			{	// 条件を満たすので、部分列の右端に追加
				psub.push_back(e);

				auto ng = [&]() -> bool { return !(true); }

				while (!psub.empty() && ng())
				{	// 条件を満たさない間、部分列の左端から削除
					psub.pop_front();
				}
			}
		};
	}
}

実装例
https://atcoder.jp/contests/abc038/submissions/33280142
https://atcoder.jp/contests/arc022/submissions/33412822