題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 ABC381F 1122 Subsequence

Problem Statement

題目簡述

給定長度為 $N$ 的序列 $A$ ，請選出一個子序列，使它可以被分成若干相鄰的相同數字對，且每種出現過的數字都恰好出現兩次。求這樣的子序列最大長度。

Constraints

約束條件

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 20$
所有輸入皆為整數

思路：狀態壓縮 DP 維護最早結尾位置

問題本質與突破口

題目要求選出一個 1122 子序列：每種被選中的數字恰好出現兩次，且這兩次必須相鄰構成一個「對」。

注意約束條件，關鍵限制是 $A_i \leq 20$ ，值域僅 20 種數字，遠小於序列長度 $N \leq 2 \times 10^5$ 。

由於每種數字只能選擇「不選（0 次）」或「選（2 次）」兩種狀態，我們可以用一個 $20$ -bit 的遮罩來表示已選數字的集合。這樣總共有 $2^{20} \approx 10^6$ 種狀態，對 DP 來說是可行的。

狀態設計：最早結尾的貪心策略

對於一個已選數字集合 $S$ ，在原序列中可能存在多種不同的 1122 子序列選法（相同集合但用不同位置）。我們需要從中選出「最有利於後續擴展」的那一種。

貪心策略的正確性

對於同一個已選集合 $S$ ，可能的結尾位置有早有晚。結尾越早，原序列剩餘可用位置越多，後續能加入的數字對也越多。因此對於每個 $S$ ，只須記錄最早可能的結尾位置——任何更晚的結尾都不會帶來更好的結果。

定義： $f[S]$ 表示選取集合 $S$ 中的數字構成合法 1122 子序列時，該子序列在陣列中的最早結尾位置（0-indexed）。
初始狀態：空集合的結尾設為 $-1$ （代表「序列開頭之前」），其餘狀態初始化為 $N$ （代表無窮大，表示尚未找到合法構造）。

轉移：加入一對新數字

假設已知狀態 $S'$ 的最早結尾位置為 $p = f[S']$ ，現在想加入數字 $x$ （ $x \notin S'$ ）形成新狀態 $S = S' \cup \{x\}$ 。

加入 $x$ 的配對必須滿足兩個條件：

兩個 $x$ 的位置都嚴格在 $p$ 之後（不與已選子序列重疊）
與前述的貪心策略類似，這裡選擇最早的兩個 $x$ 來配對，確保新狀態 $S$ 的結尾位置盡可能早。

可以預處理每個數字 $x$ 的出現位置列表，在該列表中找到第一個嚴格大於 $p$ 的位置，然後再取下一個位置作為配對的第二個元素。這樣就能確定新狀態 $S$ 的結尾位置。

DP 枚舉順序

由於 $S \setminus \{x\} \subset S$ ，其數值必定小於 $S$ 。因此可以按照遞增順序枚舉所有遮罩，保證處理 $S$ 時所有子狀態的答案已經計算完畢。

若 $f[S] < N$ （即狀態 $S$ 存在合法構造），則集合大小 $|S|$ 為可選取的數字種類數。每種數字貢獻長度 $2$ ，故總長度為 $2 \times |S|$ 。

複雜度分析

時間複雜度： $\mathcal{O}(N + K \cdot 2^K \log N)$ $O (N + K \cdot 2^{K} lo g N)$ ，其中 $K = 20$ $K = 20$ 。
- 預處理 $O(N)$ ，建立每個元素對應的位置列表；
- DP 枚舉 $2^K$ 個狀態，每個狀態遍歷其設定位元（均攤每狀態 $O(K)$ ），每次二分搜尋 $O(\log N)$ 。
空間複雜度： $\mathcal{O}(N + 2^K)$ 。位置表儲存所有 $N$ 個索引；DP 陣列大小 $2^K$ 。

Code

from bisect import bisect_left

M = 20


def solve():
    n = int(input())
    A = list(map(int, input().split()))
    assert len(A) == n

    pos = [[] for _ in range(M + 1)]
    for i, v in enumerate(A):
        pos[v - 1].append(i)

    # f[mask] = 選取集合 mask 構成 1122 子序列的最早結尾位置
    f = [n] * (1 << M)
    f[0] = -1

    ans = 0
    for s in range(1 << M):
        # 枚舉 s 中每個位元作為「最後加入的數字」，嘗試從 s\{j} 轉移
        t = s
        while t:
            lb = t & -t
            j = lb.bit_length() - 1
            # 在 j 的位置表中找第一個 > f[s\{j}] 的索引，+1 即為配對的第二個位置
            idx = bisect_left(pos[j], f[s ^ lb]) + 1
            if idx < len(pos[j]):
                f[s] = min(f[s], pos[j][idx])
            t ^= lb
        if f[s] < n:
            ans = max(ans, s.bit_count())
    print(ans << 1)


if __name__ == "__main__":
    solve()