https://torus711.hatenablog.com/entry/2024/11/23/192115

問題文

　https://atcoder.jp/contests/abc381/tasks/abc381_d

問題概要

　$n$ 項からなる正整数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ が与えられる．$A$ の連続部分列 $X$ であって，以下の条件を（すべて）満たすものの内で最長なものの長さを求めよ：

$|X| \bmod 2 = 0$
$\forall i \in \left[ 1, \frac { |X| } 2 \right], X_{ 2 i - 1 } = X_{ 2 i }$
$X$ に含まれる要素の $X$ での出現回数はちょうど $2$

制約

$1 \leq n \leq 2 \times 10^5$
$1 \leq A_i \leq n$

準備

　$A$ の（連続）部分列 $\langle A_l, A_{ l + 1 }, \dots, A_{ r - 1 } \rangle$ を $A[ l, r )$ と書くことにします．

解法

　部分列のとり方は $\Theta( n^2 )$ 個あるため，そのすべてを調べることはできません．何かしら工夫する必要があります．
　条件の observation から，ある $l, r$ ($l \leq r$) について $A[ l, r )$ が条件を満たすならば $r' = r - 2k$ ($k \in \mathbb Z_{ {>}0 }$) なる $r'$ について $A[ l, r' )$ も条件を満たし，$A[ l, r )$ が条件を満たさないならば $r' = r + 2k$ ($k \in \mathbb Z_{ {>}0 }$) なる $r'$ について $A[ l, r' )$ も条件を満たしません．よって，条件を満たさなくなる境界は一意的に定まります．また，（条件 1., 2. に違反しないように）$l$ を $2$ ずつ増加させたとき，それらに対応する境界（の位置の添字）は単調非減少です．このことから，しゃくとり法で効率化できそうな気持ちになってきます．
　「着目している部分列に含まれる要素をユニークにしたい」ならよく見る気がするのでそれと似た感じで解きたいですが，

区間の端点を $2$ ずつ動かして $2$ 個ずつまとめてカウントしたい．
異なる要素が隣接している場合も gereral に扱えるようにしたい．

という 2 つの要求はやや相性が悪そうに見えます．
　ここでは，入力を加工することで解きやすい問題に変換して解くことを試みます．条件を満たす部分列は（条件 2. から）「先頭から $2$ 要素ずつペアにするとペアの要素は一致している」という条件を満たしているはずなので，

ペアリングできる極大な列に分解する．
各列の各ペアを単一要素に潰す．

ということをすると上述の「着目している部分列に含まれる要素をユニークにしたい」という問題に帰着されます．ペアリングの方法は奇数番目を左・偶数番目を右にする方法と偶数番目を左・奇数番目を右にする方法の 2 通りがあるので両方試します．そうしてできた部分問題たちについてそれぞれ答えを求めて最大値をとることで，元の問題に答えることができます．
　部分問題は，各値が着目している区間に含まれているかどうかを判定できるようにして，重複が発生しない間右端点を伸ばすしゃくとり法で解くことができます．このとき，$A_i$ の制約から，$A_i$ を配列の添字にしようとすると初期化のコストで TLE するので，std::set で数えることにします．
　このアルゴリズムは，まず入力の加工に $\Theta( n )$ 時間がかかり，各部分問題については上述のしゃくとり法で解けます．$A$ の各要素は高々 $2$ 個の部分問題に出現し，部分問題においてはちょうど $1$ 回ずつ std::set への挿入・削除が行われるため，（前処理も含め）$O( n \log n )$ 時間となります．

コード

int solve( const VI &A )
{
	const int N = SZ( A );

	int res = 0;
	set< int > appear;
	for ( int i = 0, j = 0; i < N; ++i )
	{
		for ( ; j < N && !appear.contains( A[j] ); appear.insert( A[ j++ ] ) );
		chmax( res, j - i );
		appear.erase( A[i] );
	}

	return 2 * res;
}

int main()
{
	IN( int, N );
	VI A( N );
	cin >> A;

	int res = 0;
	REP( base, 2 )
	{
		VVI blocks;
		for ( int i = base; i + 1 < N; i += 2 )
		{
			if ( A[i] != A[ i + 1 ] )
			{
				continue;
			}

			blocks.EB();
			int j = i;
			for ( ; j + 1 < N && A[j] == A[ j + 1 ]; j += 2 )
			{
				blocks.back().PB( A[j] );
			}
			i = j;
		}

		FOR( block, blocks )
		{
			chmax( res, solve( block ) );
		}
	}

	cout << res << endl;

	return 0;
}