尺取法 auto tpt

尺取法（Two Pointer Techinique）テンプレート

auto tpt=[&](auto& seq, auto sf, auto& res)->void

seq: 入力列全体
sf: 入力列の先頭要素 (seq.front())
res: 結果

auto tpt=[&](auto& seq, auto sf, auto& res)->void {
	deque<decltype(sf)> sub;
	ここで初期化をする;

	for(auto& e:seq) {
		右手関連の処理;
		sub.push_front(e);

		while(!sub.empty()&&条件を満たさない間くり返す) {
			左手関連の処理;
			sub.pop_back();
		}

		条件を満たすので、このタイミングで res を更新;
	}
};

本質

subは右手と左手の現在範囲を表す。右手操作時はdequeの先頭にseqの要素をpushしていき、左手操作時はdequeの後尾からpopしていく。for文1回毎に右手を1要素進める。条件を満たさなくなったときwhile文に入る。while文では条件を満たさない間ずっと左手を1要素ずつ進める。while文を抜けた後は条件を満たしているので、while文を抜けた後は結果の更新タイミングになる。dequeを使うことでバグりづらくしている。また、dequeの型を指定するために引数では入力列の先頭要素も指定する。