HardRating 2272

2179. Count Good Triplets in an Array

arraybinary-searchdivide-and-conquerbinary-indexed-treesegment-treemerge-sortordered-set

解題說明

Count Good Triplets in an Array

題目描述：給定兩個長度為 n 的排列 nums1 和 nums2（都是 0 到 n-1 的排列）。一個三元組 (x, y, z) 是好的，如果 x, y, z 在 nums1 中的相對順序和在 nums2 中的相對順序相同。求好三元組的數量。

解題思路：將問題轉化為在一個序列中計算「順序對」的三元組。

建立映射：pos2[v] = v 在 nums2 中的位置。
構造序列 arr：arr[i] = pos2[nums1[i]]，即 nums1 中第 i 個元素在 nums2 中的位置。
好三元組 (x, y, z) 等價於 arr 中的遞增三元組 arr[i] < arr[j] < arr[k]（i < j < k）。
對每個位置 j，答案 += (j 左邊比 arr[j] 小的數量) * (j 右邊比 arr[j] 大的數量)。
使用 Binary Indexed Tree（BIT/樹狀陣列）：
- 從左到右掃描計算 leftSmaller[j]。
- 右邊比 arr[j] 大的數量 = (n - 1 - j) 中尚未處理的 - (比 arr[j] 小的已處理的) = (n - arr[j] - 1) - rightSmaller。用第二次掃描或公式計算。

C++ 解法

複雜度分析

時間複雜度：O(n log n) — 兩次掃描各 O(n)，每次 BIT 操作 O(log n)。

空間複雜度：O(n) — BIT 陣列和輔助陣列。

虛擬碼

1. Build pos2[v] = index of v in nums2.
2. Build arr[i] = pos2[nums1[i]].
3. First pass (left to right) with BIT:
   For each i: leftSmaller[i] = BIT.query(arr[i]-1), then BIT.update(arr[i], +1).
4. Second pass (right to left) with fresh BIT:
   For each i: rightGreater[i] = (n-1-arr[i]) - count of elements > arr[i] already in BIT.
   ans += leftSmaller[i] * rightGreater[i].
   BIT.update(arr[i], +1).
5. Return ans.

其他解法

歸併排序法：類似逆序對計數，用歸併排序在合併過程中統計符合條件的三元組。但三元組的計數比二元組（逆序對）複雜得多，實作難度高。時間複雜度 O(n log n)。
離散化 + 線段樹：使用線段樹替代 BIT，支援區間查詢和單點更新。功能上等價，但線段樹的常數因子較大，且程式碼更長。

延伸思考

若要計算「好四元組」（四個元素保持相同相對順序），如何擴展此方法？
若兩個序列不是排列而是可能有重複元素，解法需要什麼修改？
如何修改演算法以在 O(n log n) 時間內找出一個具體的好三元組（而非只計數）？

Count Good Triplets in an Array — CaffeCode