分割統治による計算量 \(O(N\log N)\) 時間での解法を紹介します．

数列 \((a_1, \ldots, a_{2i})\) に対する答を \(\mathrm{dp}[i]\) とします． また，\(\mathrm{dp}[L], \ldots, \mathrm{dp}[R-1]\) という列を単に \(\mathrm{dp}[L: R]\) と書くことにします．

[1] 方針

再帰関数 calc_dp を次のように設計します．これは，\(\mathrm{dp}[0:L]\) から \(\mathrm{dp}[L:R]\) への遷移が既に計算されているという前提条件のもと，\(\mathrm{dp}[L:R]\) を計算するものです．

def calc_dp(L, R):
    if R == L + 1: return
    M = (L + R) / 2
    calc_dp(L, M)
    （ここで dp[L:M] から dp[M:R] への遷移を計算する）
    calc_dp(M, R)    

\(\mathrm{dp}[L:M]\) から \(\mathrm{dp}[M:R]\) への遷移を \(O(R-L)\) 時間で計算することで，dp テーブル全体を \(O(N\log N)\) 時間で計算することができます．以下ではこの遷移の計算について解説します．

[2] 遷移の計算

次の手順で計算できます．

• 長さが偶数のすべての区間により遷移する
• そのうち，過半数の要素が存在するような区間による遷移を引く

前者の計算は簡単です．後者の計算を考えます．まず，過半数の要素は区間に対して 1 つ以下しかないので，各 \(x\) について \(x\) が過半数になるような区間による遷移を引けばよいです．

\(x\) が過半数であることは，\(x\) を \(+1\)，その他の値を \(-1\) に置き換えた列における総和が正であることと同値です．この列における，\([i, M)\) や \([M,j)\) 内での総和を計算しておけば，累積和を用いて遷移をまとめることは容易です．しかしこれを素直に実装すると，\(x\) ごとに計算量 \(\Theta(R-L)\) がかかってしまいます．

\(n_x\) を \([L:R)\) 内における \(x\) の個数とするとき，次の事実を利用します：

\(x\) が過半数となるような区間の長さは \(2n_x\) 未満である．

したがって \(|M-i| \leq 2n_x\) であるような \(i\) のみを計算対象として上で述べた計算すれば，この部分の計算は \(O(n_x)\) 時間で行えます．

\(\sum_x n_x = R-L\) なので，\(O(R-L)\) 時間で \(\mathrm{dp}[L:M]\) から \(\mathrm{dp}[M:R]\) への遷移を計算することができます．

なお，\([L, R)\) 内の \(x\) の重複削除などの実装によっては計算量が \(\Theta(N\log^2N)\) になってしまいますが，それでも十分 AC 可能です．