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

🔗 ABC381D 1122 Substring

Problem Statement

題目簡述

給定長度為 $N$ 的正整數序列 $A$ 。
若一個序列長度為偶數、每兩個相鄰位置成對相等，且出現過的每個數字都恰好出現兩次，則稱為 1122 序列。
請求出 $A$ 的連續子陣列中，最長 1122 序列的長度，注意答案可能為 $0$ 。

Constraints

約束條件

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

思路：依配對起點分組，做兩次滑動窗口

1122 序列要求子陣列長度為偶數，且可切成若干相鄰二元組，每組內兩元素相等、組間數字不重複。直接枚舉所有子陣列是 $\mathcal{O}(N^2)$ ，不可行。

核心觀察

一旦固定子陣列從哪種奇偶位置開始，相鄰配對方式就固定了（從 $0$ 開始則為 $(A_0,A_1),(A_2,A_3),\dots$ ；從 $1$ 開始則為 $(A_1,A_2),(A_3,A_4),\dots$ ）。合法區間必定由連續的有效二元組構成，且這些二元組的數字不得重複。

因此，分別以兩種起點掃描，每次前進兩格。在每種起點下，問題轉化為：在一串二元組上，找最長連續不重複數字區間，可用滑動窗口解決：

右端點每次向右移動兩個位置：若該組兩元素不相等，則窗口必須在此斷裂——左端點跳到下一組起點，計數器清空重來。
若兩元素相等，檢查該數字是否已在窗口內出現：若已出現，則不斷收縮左端點，直到不再重複為止。
每成功加入一組後，以目前窗口長度更新答案即可。

複雜度分析

時間複雜度： $\mathcal{O}(N)$
空間複雜度： $\mathcal{O}(N)$

Code

from collections import defaultdict


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

    def calc(st: int) -> int:
        res = 0
        left = st
        cnt = defaultdict(int)
        for i in range(st, n - 1, 2):
            x = A[i]
            if x != A[i + 1]:
                left = i + 2
                cnt.clear()
                continue
            while cnt[x] > 0:
                cnt[A[left]] -= 1
                left += 2
            cnt[x] += 1
            res = max(res, i + 2 - left)
        return res

    print(max(calc(0), calc(1)))


if __name__ == "__main__":
    solve()