MediumRating 1344
1395. Count Number of Teams
arraydynamic-programmingbinary-indexed-treesegment-tree
解題說明
Count Number of Teams
題目描述： 給定一個整數陣列 rating，選擇 3 名士兵組成一支隊伍，要求索引 (i, j, k) 滿足 i < j < k 且 rating 嚴格遞增或嚴格遞減。求總共有多少種選法。
解題思路： 對於每個中間位置 j，分別統計左邊比 rating[j] 小的數量 leftSmaller 和右邊比 rating[j] 大的數量 rightGreater，則通過 j 的遞增三元組數量為 leftSmaller × rightGreater。同理，左邊比 rating[j] 大的數量 leftGreater 和右邊比 rating[j] 小的數量 rightSmaller 相乘得到遞減三元組數量。對所有 j 求和即為答案。
C++ 解法
複雜度分析
時間複雜度：O(n²) — 對每個中間元素 j，遍歷左右兩側
空間複雜度：O(1) — 只使用常數額外空間
虛擬碼
1. For each middle index j from 1 to n-2: a. Count leftSmaller: elements before j that are smaller than rating[j] b. Count leftGreater: elements before j that are larger than rating[j] c. Count rightSmaller: elements after j that are smaller than rating[j] d. Count rightGreater: elements after j that are larger than rating[j] e. Add leftSmaller * rightGreater (ascending) + leftGreater * rightSmaller (descending) to result 2. Return result
其他解法
方法一：Binary Indexed Tree (BIT) 使用 BIT 動態維護已遍歷元素的排名。從左到右遍歷，可以用 BIT 快速查詢 leftSmaller 和 leftGreater。時間複雜度 O(n log n)，適合 n 較大的情況。
方法二：合併排序統計 類似求逆序對的方式，用修改過的合併排序來統計三元組。時間複雜度 O(n log n)，但實現複雜度較高。
延伸思考
- 如果隊伍大小不限定為 3，而是任意 k 人，如何推廣你的解法？
- 如果允許非嚴格遞增（即 rating[i] <= rating[j] <= rating[k]），答案會如何變化？
- 如何用 BIT 或線段樹將時間複雜度優化到 O(n log n)？