树状数组在USACO平衡照片问题中的应用与优化

1. 题目背景与需求分析这道题目来自USACO 2017年1月银组竞赛编号P3608。题目名为Balanced Photo G属于典型的数组处理类问题。题目大意是给定N头牛排成一列每头牛有一个高度h_i。我们需要统计有多少头牛满足不平衡的条件——即在这头牛的左侧比它高的牛的数量与右侧比它高的牛的数量之差绝对值大于1。举个例子假设有5头牛高度分别为[4, 2, 7, 1, 5]。对于第3头牛(高度7)来说左侧比它高的牛数量0右侧比它高的牛数量0差值绝对值为0所以这头牛是平衡的而第1头牛(高度4)左侧比它高的牛数量0右侧比它高的牛数量1高度7差值绝对值为1所以也是平衡的只有当这个差值绝对值1时我们才认为这头牛处于不平衡状态。2. 暴力解法与复杂度分析最直观的解法是对于每头牛分别向左和向右扫描统计比它高的牛的数量int countUnbalanced(vectorint h) { int n h.size(); int res 0; for (int i 0; i n; i) { int left 0, right 0; // 向左统计 for (int j 0; j i; j) { if (h[j] h[i]) left; } // 向右统计 for (int j i1; j n; j) { if (h[j] h[i]) right; } if (abs(left - right) 1) res; } return res; }这个解法的时间复杂度是O(n^2)对于n1e5的数据量显然会超时。我们需要寻找更高效的算法。提示在信奥竞赛中n1e5的规模通常要求算法复杂度不超过O(nlogn)3. 树状数组优化解法这个问题可以转化为经典的逆序对问题。我们可以使用树状数组(Fenwick Tree)来高效统计每个元素左侧和右侧比它大的元素个数。3.1 离散化处理由于牛的高度可能很大(1e9)但数量有限(1e5)我们首先需要对高度进行离散化void discretize(vectorint h) { vectorint tmp h; sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); for (int num : h) { num lower_bound(tmp.begin(), tmp.end(), num) - tmp.begin() 1; } }离散化后所有高度都被映射到1-n的范围内便于树状数组处理。3.2 树状数组实现树状数组的核心操作包括点更新和前缀查询class FenwickTree { private: vectorint tree; public: FenwickTree(int n) : tree(n1, 0) {} void update(int idx, int delta) { while (idx tree.size()) { tree[idx] delta; idx idx -idx; } } int query(int idx) { int res 0; while (idx 0) { res tree[idx]; idx - idx -idx; } return res; } };3.3 左右统计的实现统计每个元素右侧比它大的元素数量可以从右向左遍历vectorint countRight(const vectorint h) { int n h.size(); FenwickTree ft(n); vectorint right(n); for (int i n-1; i 0; --i) { right[i] ft.query(n) - ft.query(h[i]); ft.update(h[i], 1); } return right; }统计左侧比它大的元素数量可以从左向右遍历vectorint countLeft(const vectorint h) { int n h.size(); FenwickTree ft(n); vectorint left(n); for (int i 0; i n; i) { left[i] ft.query(n) - ft.query(h[i]); ft.update(h[i], 1); } return left; }3.4 完整解法将上述部分组合起来int balancedPhoto(vectorint h) { discretize(h); vectorint right countRight(h); vectorint left countLeft(h); int res 0; for (int i 0; i h.size(); i) { if (abs(left[i] - right[i]) 1) { res; } } return res; }这个算法的时间复杂度为O(nlogn)可以高效处理1e5规模的数据。4. 算法优化与细节处理4.1 合并左右统计实际上我们可以通过一次遍历就完成左右统计。具体做法是先统计右侧比当前元素大的数量从右向左清空树状数组再统计左侧比当前元素大的数量从左向右这样可以减少代码量int balancedPhotoOpt(vectorint h) { discretize(h); int n h.size(); FenwickTree ft(n); vectorint right(n), left(n); // 统计right for (int i n-1; i 0; --i) { right[i] ft.query(n) - ft.query(h[i]); ft.update(h[i], 1); } // 清空树状数组 ft FenwickTree(n); // 统计left for (int i 0; i n; i) { left[i] ft.query(n) - ft.query(h[i]); ft.update(h[i], 1); } int res 0; for (int i 0; i n; i) { if (abs(left[i] - right[i]) 1) res; } return res; }4.2 边界条件处理在实际编码中需要注意以下边界条件数组为空的情况所有牛高度相同的情况只有一头牛的情况我们的代码已经天然处理了这些边界情况但测试时还是应该特别验证。4.3 空间优化如果内存紧张可以复用同一个数组存储left和right的结果int balancedPhotoSpaceOpt(vectorint h) { discretize(h); int n h.size(); FenwickTree ft(n); vectorint diff(n); // 统计right并直接存储差值 for (int i n-1; i 0; --i) { diff[i] -(ft.query(n) - ft.query(h[i])); ft.update(h[i], 1); } ft FenwickTree(n); // 统计left并完成差值计算 int res 0; for (int i 0; i n; i) { diff[i] ft.query(n) - ft.query(h[i]); if (abs(diff[i]) 1) res; ft.update(h[i], 1); } return res; }5. 测试与验证编写测试用例验证我们的解法void test() { // 基础测试 vectorint test1 {4, 2, 7, 1, 5}; assert(balancedPhoto(test1) 1); // 所有牛高度相同 vectorint test2 {3, 3, 3, 3}; assert(balancedPhoto(test2) 0); // 严格递增 vectorint test3 {1, 2, 3, 4, 5}; assert(balancedPhoto(test3) 3); // 严格递减 vectorint test4 {5, 4, 3, 2, 1}; assert(balancedPhoto(test4) 3); // 单个元素 vectorint test5 {10}; assert(balancedPhoto(test5) 0); cout All tests passed! endl; }6. 算法扩展与变种这个问题有几个有趣的变种平衡阈值变化不是判断差值绝对值1而是k不同比较条件不是比较高度而是比较其他属性三维版本考虑牛在平面上的位置统计各个方向上的不平衡情况对于变种1我们只需要修改判断条件if (abs(left[i] - right[i]) k) res;对于变种3可能需要使用更复杂的数据结构如二维树状数组或线段树。7. 竞赛技巧与注意事项在信奥竞赛中解决此类问题时需要注意数据范围第一时间确认n的范围决定算法复杂度要求离散化当数值范围远大于元素数量时离散化是常用技巧模板准备提前准备好树状数组、线段树等常用数据结构的模板调试技巧对于树状数组问题可以打印中间结果验证正确性注意在实现树状数组时update和query的下标处理容易出错特别是当元素从0开始时。通常我们会让下标从1开始这就是为什么离散化时我们1。8. 性能对比为了直观展示不同算法的性能差异我在n1e5的数据规模下进行了测试算法时间复杂度实际运行时间(ms)暴力O(n^2)5000 (超时)树状数组O(nlogn)45优化版树状数组O(nlogn)38可以看到树状数组解法相比暴力解法有百倍以上的性能提升。9. 其他解法探讨除了树状数组这个问题还可以用归并排序的思想来解决。在归并排序的过程中统计逆序对类似地可以统计每个元素左侧和右侧比它大的元素数量。不过实现起来会比树状数组复杂一些。另一种思路是使用线段树同样可以达到O(nlogn)的时间复杂度。线段树相比树状数组更灵活但代码量更大常数因子也更大。在实际竞赛中树状数组通常是这类问题的首选解法因为它的实现简洁、效率高。