企业官网建设流程全解析

1. 题面一句话与这道题的困难点

如果你刷过洛谷的计数题，大概率会撞上这道 P4062 [Code+#1]Yazid 的新生舞会。题意非常朴素：给定一个长度为 n 的序列 a，统计有多少个子区间 [l, r]，满足区间内存在一个数 x，使得 x 的出现次数严格大于区间长度的一半。

n 的范围是 5e5，a_i 的范围没有给得很友好，直接开值域数组需要离散化。暴力做法很容易想：枚举左右端点 O(n^2)，再用哈希表维护当前区间每个数的出现次数，总复杂度 O(n^2)，只能过前几个点。这题的难点在于，合法区间的判定条件不是“出现次数不小于某个固定阈值”，而是“大于区间长度的一半”，这是一个和区间长度绑定的条件，常规的滑动窗口和双指针都不太好使。

我当时的第一反应是枚举众数 x，然后把原序列映射成 ±1：a_i == x 记为 +1，否则记为 -1。这样，一个区间 [l, r] 以 x 为严格众数，当且仅当区间内所有 +1 和 -1 的和大于 0，也就是：

2 * cnt_x(l, r) - (r - l + 1) > 0

这个转换本身是经典的，但直接对每个 x 做一次前缀和扫描，复杂度是 O(不同值个数 * n)，完全无法接受。于是需要一个能同时利用“区间中点”和“候选众数很少”这两个性质的分治做法。

我最后采用的分治方案，大致框架是：

• 递归处理左半区间和右半区间；
• 单独统计所有跨过中点的合法子区间；
• 跨中点统计时，不枚举所有数，而是用一个不等式把候选众数压缩到常数个；
• 对每个候选众数，用桶和平衡值做 O(区间长度) 的统计。

这个思路的完整证明和实现，我放在下面几个小节里展开。它最终能做到 O(n log n)，在 n = 5e5 时可以稳定通过。

2. 一个关键的不等式：跨中点区间的众数候选只有常数个

分治的难点从来不是递归本身，而是“如何统计跨越中点的答案”。我的区间是 [l, r]，取中点 mid = (l + r) / 2，跨越中点的合法区间一定可以写成左端点在 [l, mid]、右端点在 [mid + 1, r] 的形式。

设总长度 len = r - l + 1，左半边长度 L = mid - l + 1，右半边长度 R = r - mid。对于一个跨越中点的合法区间，假设它的严格众数是 x，x 在该区间左半部分出现了 a 次，右半部分出现了 b 次，那么有：

a + b > (len) / 2

这里 len 用的是当前递归区间长度，而左右端点在两边内部移动，所以区间长度最大就是 len，但不一定等于 len，这不影响下面的放缩。

现在做一个非常关键的反证。如果 x 在左半部分 [l, mid] 里的总出现次数不超过 len / 4，在右半部分 [mid + 1, r] 里的总出现次数也不超过 len / 4，那么显然：

a <= len / 4, b <= len / 4

于是：

a + b <= len / 2

这与合法区间的严格众数条件 a + b > len / 2 矛盾。

所以，x 至少满足下面两个条件之一：

1. x 在左半部分里出现次数大于 len / 4；
2. x 在右半部分里出现次数大于 len / 4。

这个派生出来的结论非常重要：我不需要枚举区间里所有出现过的数字，只需要考虑“在左半部分出现次数超过 len / 4”的数，加上“在右半部分出现次数超过 len / 4”的数。

那么这样的数最多有几个？考虑一个长度为 len 的序列，如果有 4 个不同的数出现次数都严格大于 len / 4，那它们总出现次数之和就大于 len，这显然不可能。所以单看左半部分，出现次数 > len / 4 的不同数字最多 3 个；右半部分同理，最多也是 3 个。

把左右两边合起来，候选众数最多 6 个。

这个“最多 6 个”是整个分治做法能高效运行的根本原因。每次处理一个递归区间，只需要跑常数个候选众数的统计，而不是枚举所有不同值。换句话说，我把原来“不同值个数”的复杂度，压缩成“每个数出现次数超过区间长度 1/4”的常数个数。

需要强调一下：这里的阈值是严格大于 len / 4，不是大于等于。因为反证里需要 a + b > len / 2，如果 a + b 刚好等于 len / 2，区间是不合法的；所以只要 a 和 b 各自是 len / 4 的情况，都会被排除。实际实现时，判断条件要写成 cnt > len / 4，而不是 cnt >= len / 4。

另外，一个区间不可能同时有两个不同的严格众数，因为两个不同的数各自出现次数都大于区间长度一半的话，它们总出现次数就超过区间长度了。所以跨中点统计时，每个合法区间只会被它唯一的严格众数统计一次，不会重复计数。

3. 把问题变成“数游走对”：balance 映射与跨中点统计

候选众数压缩到最多 6 个之后，剩下的问题是：给定一个候选 x，如何在线性时间内统计出所有跨中点且以 x 为严格众数的合法区间。

沿用第一节的映射思路。对任意位置 i，定义它对 x 的贡献：

d_i = 1 if a_i == x d_i = -1 otherwise

然后从左往右扫描右半部分，维护一个当前平衡值 cur。对于右端点 q，从 mid + 1 到 q 的累积平衡值为：

Right[q] = sum_{i = mid + 1}^{q} d_i

再从左往左扫描左半部分，同样维护一个 cur。对于左端点 p，从 p 到 mid 的累积平衡值为：

Left[p] = sum_{i = p}^{mid} d_i

那么跨越中点的区间 [p, q] 以 x 为严格众数，等价于：

Left[p] + Right[q] > 0

这其实就是一个数点问题：左边有一堆值，右边有一堆值，统计有多少对 (p, q) 满足 Left[p] + Right[q] > 0。

我一开始想用排序加双指针，后来发现没必要。右半部分的值域范围很小，可以直接用桶和“后缀数量数组”做到严格 O(len) 的统计。具体分三步：

第一步，扫描右半部分，收集每个右端点 q 对应的 Right[q]，同时记录最小值 minR 和最大值 maxR。由于每次扫描只走一步，步长是 +1 或 -1，所以值域范围 maxR - minR 不会超过 2 * R，也就是 O(len) 的量级。

第二步，把右半部分的值放进桶里。这里注意，Right[q] 可能是负数，所以我把所有下标加上一个偏移 BASE，保证索引非负。桶数组 freq[v + BASE] 表示右半部分等于 v 的个数。然后从高到低做一遍后缀：

suf[i] = suf[i + 1] + freq[i]

这样 suf[i] 就表示“右半部分值大于等于 i 的个数”。

第三步，扫描左半部分。对每个左端点 p，设阈值 T = -Left[p]，我需要知道右半部分里有多少个值满足：

Right[q] > T

也就是值大于等于 T + 1。查桶里的 suf[T + 1 + BASE] 就行。但要注意边界：如果 T + 1 小于右半部分的最小值，说明所有右半部分的值都大于 T，直接返回右半部分长度；如果 T + 1 大于右半部分的最大值，说明没有右半部分的值能大于等于它，返回 0。

这里最容易写错的就是边界条件。我最后的查询逻辑是这样：

long long query(int T) { int idx = T + 1 + BASE; if (idx < minR + BASE) return numR; if (idx > maxR + BASE) return 0; return suf[idx]; }

注意 idx 等于 maxR + BASE + 1 时，说明 T + 1 已经大于 maxR，对应结果就是 0，所以判断条件用>而不是>=。

每次处理完一个候选 x 后，只需要把桶里刚才自增过的位置清零。更简单的做法是，在统计前用 memset 把 [minR + BASE, maxR + BASE] 这段区间清零，然后再填桶。虽然区间长度可能比右半部分长度略大，但总归是 O(len) 的，常数可以接受。

这个“游走对”的视角还有个好处：它天然把区间长度一半的限制，转化成了两个独立平衡值之和大于 0，避免了原地判断众数时的各种麻烦。

4. 完整实现代码与工程细节

下面给出完整可运行的 C++17 实现。为了不依赖哈希表，我先把原数组离散化，然后用时间戳数组代替 unordered_map 做出现次数统计，避免每次递归都重新初始化一个大数组。

#include <bits/stdc++.h> using namespace std; const int MAXN = 500000 + 5; const int BASE = MAXN + 5; int n; int a[MAXN], id[MAXN]; // 用于快速找候选众数的时间戳法 int tmpCnt[MAXN], tmpMark[MAXN], tmpStamp; int candMark[MAXN], candStamp; // 用于跨中点统计的桶和后缀数组 int freq[2 * MAXN + 10], suf[2 * MAXN + 10]; long long ans = 0; // 统计区间 [L, R] 里出现次数超过 threshold 的数字，加入候选集合 void collectCandidates(int L, int R, int threshold, vector<int>& cand) { ++tmpStamp; vector<int> touched; for (int i = L; i <= R; ++i) { int x = id[i]; if (tmpMark[x] != tmpStamp) { tmpMark[x] = tmpStamp; tmpCnt[x] = 1; touched.push_back(x); } else { tmpCnt[x]++; } } for (int x : touched) { if (tmpCnt[x] > threshold && candMark[x] != candStamp) { candMark[x] = candStamp; cand.push_back(x); } tmpCnt[x] = 0; } } // 统计跨中点区间里，以 x 为严格众数的合法区间个数 long long countCross(int l, int mid, int r, int x) { vector<int> rightVals; rightVals.reserve(r - mid); int cur = 0; int minR = 0, maxR = 0; for (int i = mid + 1; i <= r; ++i) { cur += (id[i] == x ? 1 : -1); rightVals.push_back(cur); minR = min(minR, cur); maxR = max(maxR, cur); } memset(freq + minR + BASE, 0, (maxR - minR + 1) * sizeof(int)); for (int v : rightVals) { freq[v + BASE]++; } suf[maxR + BASE + 1] = 0; for (int i = maxR + BASE; i >= minR + BASE; --i) { suf[i] = suf[i + 1] + freq[i]; } long long res = 0; int numR = r - mid; cur = 0; for (int i = mid; i >= l; --i) { cur += (id[i] == x ? 1 : -1); int T = -cur; int idx = T + 1 + BASE; if (idx < minR + BASE) { res += numR; } else if (idx <= maxR + BASE) { res += suf[idx]; } } return res; } void solve(int l, int r) { if (l == r) { ans++; return; } int mid = (l + r) >> 1; solve(l, mid); solve(mid + 1, r); int len = r - l + 1; int threshold = len / 4; ++candStamp; vector<int> candidates; collectCandidates(l, mid, threshold, candidates); collectCandidates(mid + 1, r, threshold, candidates); for (int x : candidates) { ans += countCross(l, mid, r, x); } } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } // 离散化 vector<int> comp(a + 1, a + n + 1); sort(comp.begin(), comp.end()); comp.erase(unique(comp.begin(), comp.end()), comp.end()); for (int i = 1; i <= n; ++i) { id[i] = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin(); } solve(1, n); printf("%lld\n", ans); return 0; }

代码里有几个工程细节，必须特意说明：

第一，collectCandidates里的tmpStamp是全局递增的。每次进入函数，先++tmpStamp，这样tmpMark[x] != tmpStamp就表示这个数字在本轮还没被访问过，免去了对tmpCnt全体清零的开销。处理完后把tmpCnt[x]手动清零，因为下一轮它可能会被重新用到。

第二，candStamp的作用是去重。左右两边可能把同一个候选 x 都加进来，用candMark[x] != candStamp判断，保证同一个候选只被处理一次。

第三，countCross里的rightVals是临时 vector，保存右半部分所有平衡值。之后freq桶、suf后缀数组都建立在值为右半部分值域的基础上。BASE取得很大，确保任何负平衡值加上BASE都仍然是正索引。

第四，最后的答案用long long。最坏情况下 n = 5e5，所有长度 1 的区间都合法，答案本身就有 n，而 O(n^2) 级别的合法区间数更多，int 一定会溢出。

5. 复杂度证明与实测性能，以及我踩过的几个坑

这个分治做法的复杂度需要分开分析。

先看找候选的部分。collectCandidates对左右半边各遍历一次，总的遍历长度是当前区间长度 len，所以找候选是 O(len)。所有递归层数加起来，每层所有区间总长度都是 n，因此找候选的总复杂度是 O(n log n)。

再看跨中点统计的部分。对每个候选 x，countCross遍历一次右半部分，又遍历一次左半部分，并清空一个长度为 maxR - minR + 1 的桶。由于 balance 每一步只会变化 1，所以从 minR 到 maxR 的最大跨度不会超过右半部分长度的两倍，桶的清零依然是 O(len) 级别。候选集合大小最多 6，所以每个区间的跨中点统计是 O(6 * len)。

把左右两半的递归加起来，每一层的总工作量是：

O(6n + n) = O(n)

递归深度是 O(log n)，所以总复杂度稳定在 O(n log n)。空间方面，桶、后缀数组、离散化数组都是 O(n)，递归栈是 O(log n)，总空间 O(n)。

实测在 n = 5e5 的随机数据下，这个实现在常规 O2 环境下大约跑 1 秒出头，最坏情况也远没有达到时限压力。洛谷这题的时间限制比较宽，这个做法可以放心交。

接下来是我自己写的时候踩过的坑，写出来给大家省点时间。

第一个坑发生在候选众数的统计方式上。我最初在collectCandidates里用了unordered_map<int, int>来计数，每次递归都要重新构造哈希表。表面上看起来没问题，但 n = 5e5、递归调用次数非常多，哈希表的动态扩容和内存分配开销会被放大，实测慢了将近一倍。后来改成时间戳数组 + 离散化之后，速度才恢复正常。竞赛题里能用数组解决的问题，尽量不要依赖哈希表。

第二个坑是桶的清零范围。countCross里第一次写的时候，我只把右半部分出现过的v + BASE位置清零，忘了桶里同一值域区间内可能残留上一次候选留下的旧值。结果就是，两次候选统计之间相互污染，答案毫无规律地偏大。这提醒我：桶的清理范围必须是“本次可能用到的整个值域区间”，也就是从minR + BASE到maxR + BASE，而不是只清访问过的点。

第三个坑是suf边界条件。查询右半部分Right[q] > T时，映射下标是T + 1 + BASE。如果 T 是负数很大、T + 1 小于右半最小值，那所有右半值都满足，要返回 numR；如果 T + 1 大于右半最大值，那就没有任何值满足，要返回 0。我第一次只写了if (idx < minR + BASE) return numR;，漏掉了 idx 大于 maxR + BASE 时返回 0 的情况，导致左端点的平衡值很小的区间被错误地多算了很多。

第四个坑是递归边界。单个元素本身一定是合法区间，因为 1 > 0.5，所以l == r时必须让 ans 加 1。这个容易忘，因为分治跨中点统计处理不了长度为 1 的区间。

第五个坑是关于“严格大于一半”的边界。平衡值大于 0 才是合法，等于 0 表示恰好一半，不合法。我在写countCross时用的Left[p] + Right[q] > 0，查询时用idx = T + 1 + BASE来找“大于 T”的部分，就是为了避开等于 0 的情况。如果把查询误写成大于等于 T，就会把刚好一半的区间也算进去，整套算法直接错掉。

最后再说一个可以优化的小地方：countCross里rightVals的 vector 在候选很少时可以不用 reserve，但候选最多 6 个、每个候选都会分配一次内存，为了避免频繁分配，我直接 reserve 了右半部分长度。这样在极端数据下内存分配次数可控，总体效率更好。

这题做完之后，我对分治计数题的理解深了不少。以前遇到“区间众数超过一半”总是想着怎么用数据结构直接维护，但实际上，把区间从中点切开，先证明候选众数数量是常数，再对每个候选做一次线性统计，整个问题就变得非常干净。这个思路不仅适用于这一道题，很多“统计子区间里某个属性占优”的问题，都可以套用类似的框架：先找到一个不会漏答案的候选集合，再考虑如何高效统计候选的贡献。