条件の言い換え等

\(X\) が良い数列である条件は次のように言い換えられます。

• \(|X|\) が偶数かつ、過半数を占める値が存在しない

\(|X|\) が偶数という条件より、\(p_i = (x_i,y_i )= (a_{2i-1},a_{2i})\) とし、\(p_1,p_2,\ldots,p_N\) を非空部分列に分割する方法を考えることにします。

\(\mathrm{O}(N^2)\) 解法

まず、想定解に繋がる \(\mathrm{O}(N^2)\) 解法を紹介します。
連続部分列 \(p_i,\ldots,p_j\) が良い数列でないとは、次のことを指します。

• ある整数 \(v(1 \leq v \leq 2N)\) が存在して、\(v\) が \(p_i,\ldots,p_j\) の過半数を占める

各 \(v\) に対し、\(x_i=v\) かつ \(y_i=v\) ならば \(1\)、\(x_i \neq v\) かつ \(y_i \neq v\) ならば \(-1\)、どちらでもなければ \(0\) を \(i\) に対する値とすると、\(v\) に対する条件はさらに次のように言い換えられます。

• \(i,i+1,\ldots,j\) に対する値の総和が \(1\) 以上である

\(\mathrm{dp}_i\) を \(p_1,\ldots,p_i\) を良い数列に分割する方法とします。各 \(v\) に対して「\(1,2,\ldots,i\) に対する値の総和 \(s\)」「\(1,2,\ldots,j\) に対する値の総和が \(i\) であるような \(j\) に対する \(\mathrm{dp_j}\) の総和 \(memo_i\)」「\(s-j \gt 1\) を満たす \(j\) に対する \(memo_j\) の総和」を持ちながら包除を行うことで全体で \(\mathrm{O}(N^2)\) で遷移を行えます。

\(\mathrm{O}(N)\) 解法

\(v\) に対し、\(v\) が過半数となる可能性がある区間に含まれるインデックスの集合を求めることを考えます。特に、\(i\) に対する値が \(0\) 以下であるような \(i\) を含む区間であって \(v\) が過半数を占めるものが存在するかどうかが気になります。
\(i\) を含む区間であって \(v\) が過半数を占めるものが存在する時、以下の少なくとも一方が成り立ちます。

• \(l(\lt i)\) に対する値が \(1\) であるような区間 \([l,i]\) であって、値の総和が \(0\) 以上であるようなものが存在する
• \(r(\gt i)\) に対する値が \(1\) であるような区間 \([i,r]\) であって、値の総和が \(0\) 以上であるようなものが存在する

このことから、\(v\) ごとに \(p_i=(v,v)\) なる \(i\) の昇順に適切な処理をすることで各 \(j\) に対して \([l,j]\) に対する値の総和の最大値を求められます。同様に、\(i\) の降順に処理を行うことで各 \(j\) に対して \([j,r]\) に対する値の総和の最大値を求められます。
また、それぞれ値の最大値が負であるような箇所については処理を打ち切れます。上記処理を考えると \(x_i \neq v\) かつ \(y_i \neq v\) にも関わらず \(v\) が過半数を占める区間に含まれ得る \(i\) は \(x_j = v\) かつ \(y_j = v\) であるような \(j\) の個数の定数倍で抑えられ、すべての \(v\) で考えても \(\mathrm{O}(N)\) となります。
よって、各 \(v\) について \(v\) が過半数となる区間に含まれ得るインデックスの集合にあたるいくつかの区間を求め、そこでのみ \(\mathrm{O}(N^2)\) 解法と同様の包除を行うことで \(\mathrm{O}(N)\) で本問を解くことができます。