如何高效统计数组中符合(a,b,b)格式的有序不同三元组（N≤1e6）

嘿，我来帮你解决这个问题！首先得明确你的核心需求：要找的是不同的(a,b,b)三元组，其中必须存在数组中的三个位置i<j<k，使得arr[i]=a、arr[j]=arr[k]=b，且a≠b。你的第二个解法出错的原因是只看了元素的出现频率，完全忽略了顺序——比如数组[3,3,5]里，虽然3出现了两次，但5在所有3的后面，根本没法形成(5,3,3)这样的有序三元组，但你的代码会错误地把它算进去。

接下来，我给你梳理正确的高效思路，时间复杂度是O(n log n)，完全能处理1e6规模的数组：

核心思路 #

我们可以把问题转化为统计所有满足以下条件的不同(a,b)对：

1. b在数组中至少出现两次；
2. a的第一次出现位置，早于b的第二次出现位置（这样必然存在i<j<k：i是a的第一次出现位置，j是b的第二次出现位置，k是b的第三次及以后的位置）；
3. a≠b。

具体步骤 #

1. 预处理关键位置：遍历数组一次，记录每个元素的第一次出现位置、第二次出现位置，以及每个元素的出现次数。
2. 收集并排序b的第二次出现位置：把所有出现至少两次的元素的第二次出现位置整理成列表并排序，方便后续二分查找。
3. 统计有效(a,b)对：对于每个不同的a，用二分查找快速计算有多少个b满足“b的第二次出现位置晚于a的第一次出现位置”，把这些数量加起来，最后减去a=b的情况（因为我们需要排除a和b相同的情况）。

代码实现 #

import bisect
from collections import defaultdict

def solve():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    arr = list(map(int, input[1:n+1]))
    
    first_occurrence = dict()
    second_occurrence = dict()
    count = defaultdict(int)
    
    for idx, num in enumerate(arr):
        if num not in first_occurrence:
            first_occurrence[num] = idx
            count[num] = 1
        else:
            count[num] += 1
            if count[num] == 2:
                second_occurrence[num] = idx
    
    # 收集所有b的第二次出现位置，排序
    p_list = sorted(second_occurrence.values())
    total_b = len(p_list)
    sum_total = 0
    
    # 遍历所有不同的a
    for a in first_occurrence:
        fa = first_occurrence[a]
        # 找到第一个大于fa的p的位置，后面的都满足p>fa
        pos = bisect.bisect_right(p_list, fa)
        sum_total += (total_b - pos)
    
    # 减去a=b的情况，每个出现≥2次的b都被算了一次a=b的情况
    ans = sum_total - len(second_occurrence)
    print(ans)

solve()

代码解释 #

• 预处理部分：用三个字典分别记录每个元素的首次出现位置、第二次出现位置，以及出现次数。当元素第二次出现时，记录它的索引到second_occurrence。
• 排序p_list：把所有符合条件的b的第二次出现位置排序，这样可以用二分查找快速统计有多少个b的第二次出现位置晚于a的首次出现位置。
• 二分查找统计：对于每个a，用bisect_right找到第一个大于fa的位置，total_b - pos就是满足条件的b的数量。
• 去重a=b的情况：因为sum_total里包含了a=b的情况（比如b出现两次，a=b时fa < p_b），所以要减去这些情况的数量，也就是len(second_occurrence)。

测试你的例子 #

对于数组[5,6,7,3,3,3]：

• first_occurrence是{5:0,6:1,7:2,3:3}；
• second_occurrence是{3:4}；
• p_list是[4]；
• 每个a对应的统计：
  • a=5：fa=0，bisect_right([4],0)=0，贡献1；
  • a=6：fa=1，贡献1；
  • a=7：fa=2，贡献1；
  • a=3：fa=3，贡献1；
• sum_total=4，减去1（len(second_occurrence)），得到3，和你的例子答案一致。

这样处理下来，时间复杂度主要是排序的O(m log m)（m是出现≥2次的元素数量）和二分查找的O(k log m)（k是不同元素数量），整体是O(n log n)，完全能应对1e6的数组规模。

备注：内容来源于stack exchange，提问作者vijaysrinivasan Thirumalai