登录
枚举 & 线段树 & 二分
解法：枚举 & 线段树 & 二分
简化问题
先考虑一个简化版的问题：求最长的子数组，使得其中偶数的数量等于奇数的数量。
这个简化版问题和上周的 leetcode 3714. 最长的平衡子串 II 非常相似：把奇数看成 $1$，偶数看成 $-1$，求的其实就是“最长的和为 $0$ 的子数组”。详见 leetcode 560. 和为 K 的子数组。
简单来说，这个问题可以用前缀和求解：设 $s_i$ 表示长度为 $i$ 的前缀的元素和，若子数组 $(l, r]$ 的元素和为 $0$，则有 $s_r - s_l = 0$，即 $s_l = s_r$。为了让子数组的长度 $(r - l)$ 最大，我们可以用哈希表维护每种 $s_l$ 对应的最小 $l$。
原问题
回到原问题。现在只统计不同的偶数和不同的奇数，怎么做？
首先，和子数组里的元素种数有关的题目，应该马上想到经典问题“luo 谷 P1972 - [SDOI2009] HH 的项链”：从左到右枚举子数组的右端点，对于每种数，只把它最近出现的位置设为 $\pm 1$，其它位置都设为 $0$。
这样，问题就变成了动态版的“求最长的和为 $0$ 的子数组”：给定一个序列，每次操作可能把一个 $0$ 变成 $\pm 1$，或把一个 $\pm 1$ 变成 $0$。每次询问给定一个前缀和目标值 $s_r$，找出 $s_l = s_r$ 的最小下标 $l$。
元素的修改可以用线段树来维护，可是最小下标该怎么找呢？其实，元素范围在 $[-1, 1]$ 里的序列有一个非常强的性质：由于每移动一位，前缀和的变化最多为 $1$，因此 在一个区间内，前缀和是连续的。
所以，我们只需要在线段树的每个节点上，记录当前区间的最小前缀和 $x$ 和最大前缀和 $y$，只要 $x \le s_r \le y$，那么区间内一定存在一个下标 $l$，满足 $s_l = s_r$。所以在线段树上二分，即可找到这个下标。详见参考代码。
复杂度 $\mathcal{O}(n\log n)$。
参考代码（c++）
class Solution {
public:
int longestBalanced(vector<int>& nums) {
int n = nums.size();
// 线段树节点，记录当前区间前缀和的最小值与最大值
struct Node {
int mn, mx, lazy;
void apply(int x) {
mn += x;
mx += x;
lazy += x;
}
} tree[(n + 1) * 4 + 5];
auto merge = [&](Node nl, Node nr) {
return Node {
min(nl.mn, nr.mn),
max(nl.mx, nr.mx),
0
};
};
// 线段树建树
auto build = [&](this auto &&build, int id, int l, int r) -> void {
if (l == r) tree[id] = Node {0, 0, 0};
else {
int nxt = id << 1, mid = (l + r) >> 1;
build(nxt, l, mid); build(nxt | 1, mid + 1, r);
tree[id] = merge(tree[nxt], tree[nxt | 1]);
}
};
// 懒标记下推
auto down = [&](int id) {
if (tree[id].lazy == 0) return;
int nxt = id << 1;
tree[nxt].apply(tree[id].lazy);
tree[nxt | 1].apply(tree[id].lazy);
tree[id].lazy = 0;
};
// 给区间 [ql, qr] 的前缀和都加上 qv
auto modify = [&](this auto &&modify, int id, int l, int r, int ql, int qr, int qv) -> void {
if (ql <= l && r <= qr) tree[id].apply(qv);
else {
down(id);
int nxt = id << 1, mid = (l + r) >> 1;
if (ql <= mid) modify(nxt, l, mid, ql, qr, qv);
if (qr > mid) modify(nxt | 1, mid + 1, r, ql, qr, qv);
tree[id] = merge(tree[nxt], tree[nxt | 1]);
}
};
// 线段树上二分，求前缀和等于 qv 的最小下标
auto query = [&](this auto &&query, int id, int l, int r, int qv) -> int {
if (l == r) return l;
down(id);
int nxt = id << 1, mid = (l + r) >> 1;
// 只要一个区间满足 mn <= qv <= mx，那么一定存在一个等于 qv 的值
// 为了让下标最小，只要左子区间满足，就去左子区间里拿答案，否则才去右子区间拿答案
if (tree[nxt].mn <= qv && qv <= tree[nxt].mx) return query(nxt, l, mid, qv);
else return query(nxt | 1, mid + 1, r, qv);
};
build(1, 0, n);
// now：目前的前缀和
int ans = 0, now = 0;
// mp[x]：元素 x 最近出现在哪个下标
unordered_map<int, int> mp;
// 枚举子数组右端点
for (int i = 1; i <= n; i++) {
int x = nums[i - 1];
int det = (x & 1 ? 1 : -1);
if (mp.count(x)) {
// 元素 x 之前出现过了，把那个位置改成 0
modify(1, 0, n, mp[x], n, -det);
now -= det;
}
// 把元素 x 当前出现的位置改成 +-1
mp[x] = i;
modify(1, 0, n, i, n, det);
now += det;
int pos = query(1, 0, n, now);
ans = max(ans, i - pos);
}
return ans;
}
};
不会做怎么办
本题的综合性比较强，需要读者掌握大量套路，我们逐个分解。
首先，如果读者不会做简化问题（即去掉“不同”的限制），说明读者没有掌握用前缀和 + 哈希表的方式，求特定子数组数量或最大长度的方法。读者可以学习 灵神题单 - 常用数据结构 的“前缀和与哈希表”一节。
接下来，如果读者看到“子数组里的不同元素”，没有马上反映出对应套路，需要复习“luo 谷 P1972 - [SDOI2009] HH 的项链”，并额外练习以下题目：
- CF gym 104459 E - [SDCPC2019] BaoBao Loves Reading：可以转化为子数组的不同元素数目。
- leetcode 2916. 子数组不同元素数目的平方和 II：一道比较综合的题目。
最后，如果读者没有意识到“元素范围在 $[-1, 1]$ 内的序列，在一个区间内，前缀和是连续的”，我暂时没有找到直接相关的练习题。可以练习 leetcode 2488. 统计中位数为 K 的子数组 一题，允许存在相同元素的加强版，并尝试用线性复杂度解答。我的题解 可供参考。
