解题思路

前缀异或建模。 设前缀异或 p[i] = a1 xor a2 xor … xor ai（p[0]=0）。把数组划分为若干连续子段，对应的是选取分割点 0=i0<i1<…<im=n，第 k 段的异或值为 s_k = p[ik] xor p[ik-1]。因此问题化为：在前缀序列 p[0..n] 上选点，使相邻点的“异或差”序列 s1..sm 构成**驼峰（交替上升/下降）**序列，且段数 m 最大。

值域仅 0..255 的关键性质。 因为 ai∈[0,255]，任意前缀异或 p[i] 也在 0..255。这使得可以用“值压缩 DP”，在每个前缀值上聚合最优状态，从而把状态数量限制在常数级（256）。

状态设计（仅记录“上/下”最后一跳）。 我们在每个可能的前缀值 α(0..255) 上维护三类信息：

• up[α][v]：到达某个位置 j，且 p[j]=α，并且最后一跳是“上升”（前一段值 < v）且最后一段值为 v 时，能取得的最大段数（≥2）。
• down[α][v]：同理，最后一跳是“下降”且最后一段值为 v 的最大段数（≥2）。
• seen[α]：是否出现过某个 j≥1 使得 p[j]=α。这相当于记录长度为 1 的序列（只有一段），其最后段值就是 α：[α]。

为实现 O(1) 级查询“比某值小/大的最大值”，额外维护：

• downPref[α][x] = max_{v≤x} down[α][v]（前缀最大）；
• upSuf[α][x] = max_{v≥x} up[α][v]（后缀最大）。

转移（在位置 i 结束一段）。 令 α_cur = p[i]。若上一段结束在某个 j<i 且 p[j]=α0，则当前段异或值 s = p[i] xor p[j] = α_cur xor α0。因此对每个候选段值 s∈[0,255]，只需取 α0 = α_cur xor s，查询此前所有 j 中前缀值为 α0 的最佳状态即可（无需遍历全部 j）。

得到两类转移（严格不等）：

• 使最后一跳为上升： up_new[s] = max( 1 + max_{u<s} down[α0][u], 2 if seen[α0] and α0 < s )
• 使最后一跳为下降： down_new[s] = max( 1 + max_{u>s} up[α0][u], 2 if seen[α0] and α0 > s )

其中 2 来自于用一段 [α0] 接上本段 s 组成两段，两段时不需要满足驼峰不等式（长度 2 真值空，即不设约束），但若后续还要接第三段，则不等式才开始起作用。 为方便实现，两段“相等”的情况（α0==s）不能继续扩展，但对最终答案若 n≥2 依然保证至少能取 2 段（任意分一次即可），因此每步答案也取 max(2, …)（当 i=1 只取 1）。

把 up_new[]/down_new[] 合并到 α_cur 的全局表里，并更新该 α_cur 的前缀/后缀最大值数组，供后续位置 i+1 查询。最终答案取恰在 i=n 结束时的最大值（可由 up_new/down_new 与长度 1/2 的兜底得到）。

复杂度。 每个位置只需遍历 s=0..255 共 256 次，查询均为 O(1)（数组访问），并且仅对 α_cur 重算一次 256 长度的前/后缀最大值。因此总复杂度 O(n·256)，常数小、实现稳定。

复杂度分析

• 时间复杂度：O(n · 256)，其中 n 为数组长度，总体（所有测试）Σn ≤ 2×10^5，常数为 256，可轻松通过。
• 空间复杂度：O(256 · 256) 用于 up/down 以及其前/后缀最大值，常数级（C++/Java 约 1MB 量级；Python 可用稠密数组优化）。

代码实现

Python

# -*- coding: utf-8 -*-
# 题意：最大化把数组分成若干连续段，使这些段的异或值序列成为驼峰（交替上/下）序列
# 思路：前缀异或 + 值域(0..255)状态DP + 每个前缀值维护“最后一跳为上/下”的最优，
#      并用前缀/后缀最大值实现 O(1) 比较查询。详见题解思路部分。

import sys
from array import array

def solve_one(arr):
    n = len(arr)
    # 计算前缀异或
    P = array('I', [0]) * (n + 1)
    for i in range(1, n + 1):
        P[i] = P[i - 1] ^ arr[i - 1]

    SIZE = 256

    # 全局状态表：为节省内存，用 array('I')，每个元素 4 字节
    up = [array('I', [0] * SIZE) for _ in range(SIZE)]
    down = [array('I', [0] * SIZE) for _ in range(SIZE)]
    downPref = [array('I', [0] * SIZE) for _ in range(SIZE)]
    upSuf = [array('I', [0] * SIZE) for _ in range(SIZE)]
    seen = [False] * SIZE

    ans = 1  # 至少可以整段不切分

    for i in range(1, n + 1):
        a_cur = P[i]

        up_new = array('I', [0] * SIZE)
        down_new = array('I', [0] * SIZE)

        # 枚举当前段的异或值 s (0..255)
        # 对应上一段结束点前缀值 a0 = a_cur xor s
        for s in range(SIZE):
            a0 = a_cur ^ s

            # 从“最后一跳为下降”的状态接一个“上升”
            if s > 0:
                best_down_less = downPref[a0][s - 1]  # max_{u<s} down[a0][u]
                if best_down_less > 0:
                    val = 1 + best_down_less
                    if val > up_new[s]:
                        up_new[s] = val

            # 从“最后一跳为上升”的状态接一个“下降”
            if s < 255:
                best_up_greater = upSuf[a0][s + 1]    # max_{u>s} up[a0][u]
                if best_up_greater > 0:
                    val = 1 + best_up_greater
                    if val > down_new[s]:
                        down_new[s] = val

            # 从长度=1的序列 [a0] 接一段 s，得到长度=2（不需要不等式）
            if seen[a0]:
                if a0 < s:
                    if 2 > up_new[s]:
                        up_new[s] = 2
                elif a0 > s:
                    if 2 > down_new[s]:
                        down_new[s] = 2
                # a0 == s：长度为2但相等，不能继续扩展，这里不存进 up/down

        # 以 i 作为结尾时的最好答案
        ans_here = max( (1 if i == 1 else 2), max(up_new, default=0), max(down_new, default=0) )
        if i == n:
            ans = ans_here

        # 合并到全局，供后续位置使用
        uarr = up[a_cur]
        darr = down[a_cur]
        changed = False
        for s in range(SIZE):
            v = up_new[s]
            if v > uarr[s]:
                uarr[s] = v
                changed = True
            v = down_new[s]
            if v > darr[s]:
                darr[s] = v
                changed = True

        # 记录出现过长度=1 的末段值 [a_cur]
        if not seen[a_cur]:
            seen[a_cur] = True
            changed = True

        # 仅当这一前缀值发生变化时，更新该行的前/后缀最大值
        if changed:
            # down 的前缀最大值
            pref = 0
            dp = down[a_cur]
            dpr = downPref[a_cur]
            for x in range(SIZE):
                if dp[x] > pref:
                    pref = dp[x]
                dpr[x] = pref
            # up 的后缀最大值
            suf = 0
            ua = up[a_cur]
            usr = upSuf[a_cur]
            for x in range(SIZE - 1, -1, -1):
                if ua[x] > suf:
                    suf = ua[x]
                usr[x] = suf

    return ans

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    t = data[0]
    idx = 1
    out_lines = []
    for _ in range(t):
        n = data[idx]; idx += 1
        arr = data[idx:idx + n]; idx += n
        out_lines.append(str(solve_one(arr)))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

// 思路同 Python：前缀异或 + 值域DP(0..255)，在每个前缀值α上维护
// up[α][v], down[α][v] 以及它们的前/后缀最大值，逐位更新。
// Java 采用简易快读以适应 Σn<=2e5 的数据量。

import java.io.*;
import java.util.*;

public class Main {
    static final int SIZE = 256;

    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= 32);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > 32) {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder sb = new StringBuilder();

        int T = fs.nextInt();

        // 全局静态表（在每个用到的 α 行上覆盖写）
        int[][] up = new int[SIZE][SIZE];
        int[][] down = new int[SIZE][SIZE];
        int[][] downPref = new int[SIZE][SIZE];
        int[][] upSuf = new int[SIZE][SIZE];
        boolean[] seen = new boolean[SIZE];

        for (int tc = 0; tc < T; tc++) {
            int n = fs.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = fs.nextInt();

            int[] P = new int[n + 1];
            for (int i = 1; i <= n; i++) P[i] = P[i - 1] ^ a[i - 1];

            // 记录本测试用例用到过的 α，结束时清零这些行，避免 O(256^2) 的全清。
            boolean[] touched = new boolean[SIZE];
            int[] upNew = new int[SIZE];
            int[] downNew = new int[SIZE];

            int ans = 1;

            for (int i = 1; i <= n; i++) {
                int aCur = P[i];

                // 清零临时转移数组
                Arrays.fill(upNew, 0);
                Arrays.fill(downNew, 0);

                for (int s = 0; s < SIZE; s++) {
                    int a0 = aCur ^ s;

                    // 从 down 过来走“上升”
                    if (s > 0) {
                        int bestDownLess = downPref[a0][s - 1];
                        if (bestDownLess > 0) {
                            int val = 1 + bestDownLess;
                            if (val > upNew[s]) upNew[s] = val;
                        }
                    }
                    // 从 up 过来走“下降”
                    if (s < 255) {
                        int bestUpGreater = upSuf[a0][s + 1];
                        if (bestUpGreater > 0) {
                            int val = 1 + bestUpGreater;
                            if (val > downNew[s]) downNew[s] = val;
                        }
                    }
                    // 从长度=1 的 [a0] 接一段 s -> 两段
                    if (seen[a0]) {
                        if (a0 < s) {
                            if (2 > upNew[s]) upNew[s] = 2;
                        } else if (a0 > s) {
                            if (2 > downNew[s]) downNew[s] = 2;
                        }
                    }
                }

                int bestHere = (i == 1 ? 1 : 2);
                for (int s = 0; s < SIZE; s++) {
                    if (upNew[s] > bestHere) bestHere = upNew[s];
                    if (downNew[s] > bestHere) bestHere = downNew[s];
                }
                if (i == n) ans = bestHere;

                // 合并入全局
                boolean changed = false;
                for (int s = 0; s < SIZE; s++) {
                    if (upNew[s] > up[aCur][s]) { up[aCur][s] = upNew[s]; changed = true; }
                    if (downNew[s] > down[aCur][s]) { down[aCur][s] = downNew[s]; changed = true; }
                }
                if (!seen[aCur]) { seen[aCur] = true; changed = true; }
                if (changed) {
                    // 更新 down 的前缀最大
                    int pref = 0;
                    for (int v = 0; v < SIZE; v++) {
                        if (down[aCur][v] > pref) pref = down[aCur][v];
                        downPref[aCur][v] = pref;
                    }
                    // 更新 up 的后缀最大
                    int suf = 0;
                    for (int v = SIZE - 1; v >= 0; v--) {
                        if (up[aCur][v] > suf) suf = up[aCur][v];
                        upSuf[aCur][v] = suf;
                    }
                }
                touched[aCur] = true;
            }

            sb.append(ans).append('\n');

            // 清理用到的 α 行
            for (int aCur = 0; aCur < SIZE; aCur++) if (touched[aCur]) {
                Arrays.fill(up[aCur], 0);
                Arrays.fill(down[aCur], 0);
                Arrays.fill(downPref[aCur], 0);
                Arrays.fill(upSuf[aCur], 0);
                seen[aCur] = false;
            }
        }

        System.out.print(sb.toString());
    }
}

C++

// 前缀异或 + 256 状态 DP：
// 对每个前缀值 α 维护 up[α][v], down[α][v] 以及它们的前/后缀最大值，
// 每到一个位置 i，仅枚举 s=0..255 一次，查询 α0 = α_cur xor s 的聚合表即可。

#include <bits/stdc++.h>
using namespace std;

static const int SIZE = 256;

int upArr[SIZE][SIZE];
int downArr[SIZE][SIZE];
int downPref[SIZE][SIZE];
int upSuf[SIZE][SIZE];
bool seenArr[SIZE];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int n; cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        vector<int> P(n + 1, 0);
        for (int i = 1; i <= n; ++i) P[i] = P[i - 1] ^ a[i - 1];

        // 为减少清零开销，记录本用例用到过的 α
        vector<int> touched;
        vector<char> touchedFlag(SIZE, 0);

        int ans = 1;
        int upNew[SIZE], downNew[SIZE];

        for (int i = 1; i <= n; ++i) {
            int aCur = P[i];
            if (!touchedFlag[aCur]) { touchedFlag[aCur] = 1; touched.push_back(aCur); }

            // 清零临时转移数组
            memset(upNew, 0, sizeof(upNew));
            memset(downNew, 0, sizeof(downNew));

            for (int s = 0; s < SIZE; ++s) {
                int a0 = aCur ^ s;

                // 从 down 过来走“上升”
                if (s > 0) {
                    int bestDownLess = downPref[a0][s - 1];
                    if (bestDownLess > 0) {
                        int val = 1 + bestDownLess;
                        if (val > upNew[s]) upNew[s] = val;
                    }
                }
                // 从 up 过来走“下降”
                if (s < 255) {
                    int bestUpGreater = upSuf[a0][s + 1];
                    if (bestUpGreater > 0) {
                        int val = 1 + bestUpGreater;
                        if (val > downNew[s]) downNew[s] = val;
                    }
                }
                // 从长度=1 的 [a0] 接一段 s -> 两段
                if (seenArr[a0]) {
                    if (a0 < s) {
                        if (2 > upNew[s]) upNew[s] = 2;
                    } else if (a0 > s) {
                        if (2 > downNew[s]) downNew[s] = 2;
                    }
                }
            }

            int bestHere = (i == 1 ? 1 : 2);
            for (int s = 0; s < SIZE; ++s) {
                if (upNew[s] > bestHere) bestHere = upNew[s];
                if (downNew[s] > bestHere) bestHere = downNew[s];
            }
            if (i == n) ans = bestHere;

            // 合并到全局
            bool changed = false;
            for (int s = 0; s < SIZE; ++s) {
                if (upNew[s] > upArr[aCur][s]) { upArr[aCur][s] = upNew[s]; changed = true; }
                if (downNew[s] > downArr[aCur][s]) { downArr[aCur][s] = downNew[s]; changed = true; }
            }
            if (!seenArr[aCur]) { seenArr[aCur] = true; changed = true; }
            if (changed) {
                // 更新 down 的前缀最大
                int pref = 0;
                for (int v = 0; v < SIZE; ++v) {
                    pref = max(pref, downArr[aCur][v]);
                    downPref[aCur][v] = pref;
                }
                // 更新 up 的后缀最大
                int suf = 0;
                for (int v = SIZE - 1; v >= 0; --v) {
                    suf = max(suf, upArr[aCur][v]);
                    upSuf[aCur][v] = suf;
                }
            }
        }

        cout << ans << "\n";

        // 清理用到的 α 行，避免影响下个测试
        for (int aCur : touched) {
            memset(upArr[aCur], 0, sizeof(upArr[aCur]));
            memset(downArr[aCur], 0, sizeof(downArr[aCur]));
            memset(downPref[aCur], 0, sizeof(downPref[aCur]));
            memset(upSuf[aCur], 0, sizeof(upSuf[aCur]));
            seenArr[aCur] = false;
        }
    }
    return 0;
}

题目内容

给定一个长度为 $n$ 的整数数组 {$a_1,a_2,...,a_n$}，其中每个元素 $a_i$ 的取值范围为 $0≦a_i≦255$ ；

你需要将该数组划分为若干个互不相交的非空连续子段，这些子段按照在原数组中的顺序排列后，其按位异或 $(xor)$ 结果必须构成一个驼峰序列；

求最多可以划分出多少个这样的子段。

驼峰序列：对于一个序列 {$b_1,b_2,...,b_m$} 如果其为驼峰序列，那么対于仼意的 $1<i< m$ 都有 $b_{i-1}<b_i>b_{i+1}$ 或者 $b_{i-1}>b_i<b_{i+1}$。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数 $t(1≦t≦ 1000)$ ，表示测试用例的组数：

此后 $t$ 组测试数据描述如下：

第一行输入一个整数 $n(1≦n≦2× 10^5)$ ，表示数组长度；

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(0≦a_i≦255)$，表示数组元素；

除此之外，保证所有测试用例的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，输出一个整数，表示最大可划分出的满足条件的子段数量。

样例1

输入

3
6
1 2 3 0 1 3
4
0 0 0 0
1
85

输出

3
2
1

说明

在第一组数据中，数组 {$1,2,3,0,1,3$} 可以划分为 {$1$},{$2$},{$3,0,1,3$}，按位异或结果为 $1,2,1$，是驼峰序列。

在第二组数据中，数组 {$0,0,0,0$} 可以划分为 {$0,0$},{$0,0$} ，对于任意的 $1<i< m$ 均满足条件(因为找不到满足 $1<i<m$ 的 $i$ ) 。