第四题 - A24633.独特三元组 题目链接跳转：A24633.独特三元组 这道题有很多做法，这里提供一个基于排列组合的算法。 假设有 NNN 个元素，且每个元素各不相同，那么满足题目要求的三元组数量就是这 NNN 个元素中任意取 333 个元素的组合。也就是 (n3)=n×(n−1)×(n−2)/1\binom{n}{3} = n \times (n-1) \times (n-2) / 1(3n )=n×(n−1)×(n−2)/1 。 如果有重复的元素呢？我们只需要把重复的元素再“去除”掉就行。 具体地说，如果某个元素的出现次数 arr[i] 大于等于 333，则可以从这些重复的元素中选出三个元素组成一个三元组 (Ai,Ai,Ai)(A_i,A_i,A_i)(Ai ,Ai ,Ai )，这是不符合条件的，因此再删除掉这些重复元素的组合数即可。即 (arr[i]3)\binom{arr[i]}{3}(3arr[i] )。 如果某个元素的出现次数 arr[i] 大于等于 222，则可以从这些重复的元素中选出两个元素，再从数组中的其他元素中选出一个不同的元素组成三元组 (Ai,Ai,Aj)(A_i,A_i,A_j)(Ai ,Ai ,Aj )，其中 Ai≠AjA_i \neq A_jAi =Aj ，即 (arr[i]2)\binom{arr[i]}{2}(2arr[i] ) 。 最后本题的 AC 代码如下：

容易想到的方法是 O(n3)O(n^3)O(n3) 暴力枚举，但是看数据范围直接再见。 比较容易想到的方法是 O(n2)O(n^2)O(n2) 组合计数，但是看数据范围也可以再见。 不是很容易想到的方法之一是二分优化组合计数，时间复杂度是 O(nlog⁡n)O(n\log n)O(nlogn)，可以通过。 不是很容易想到的方法之二是前缀和优化组合计数，时间复杂度是 O(n)O(n)O(n)，可以通过。 因为标题是前缀和优化计数，所以这里讲第四种。 首先想 O(n2)O(n^2)O(n2) 的：我们先用一个桶 BBB 进行计数。然后，我们枚举 jjj。这个时候我们可以令 iii 的选择数量就是严格小于 jjj 的数的数量，kkk 的选择数量就是严格大于 jjj 的数的数量。原因很简单，原文的限制条件令每个三元组只被选到一次，我们改变的限制条件同样令每个三元组只被选到一次，所以两者本质相同。根据组合数学的乘法原理，答案即为： ∑i∈a(∑j=1i−1bj)×bi×(∑j=i+1∞bj)\sum_{i\in a}\left(\sum_{j=1}^{i-1}b_j\right)\times b_i\times \left(\sum_{j=i+1}^\infty b_j\right) i∈a∑ (j=1∑i−1 bj )×bi ×(j=i+1∑∞ bj ) （在此 ∞\infty∞ 取 2×1052\times 10^52×105 即可。） 显然括号里的两团式子可以用前缀和 O(1)O(1)O(1) 搞掉。代码就很简单了。 双倍经验：ABC252D

题目解析 可以将问题转化为：“求满足 Ai<Aj<AkA_i \lt A_j \lt A_kAi <Aj <Ak 的三元组 (i,j,k)(i, j, k)(i,j,k) 的数量”。 > 对于满足题目原条件的三元组 (i,j,k)(i,j,k)(i,j,k)，有且仅有一个 [Ai,Aj,Ak][A_i, A_j, A_k][Ai ,Aj ,Ak ] 的排列 PPP，使得 AP1<AP2<AP3A_{P_1} \lt A_{P_2} \lt A_{P_3}AP1 <AP2 <AP3 。 > 反之，对于有 Ai<Aj<AkA_i\lt A_j\lt A_kAi <Aj <Ak 的三元组 (i,j,k)(i,j,k)(i,j,k)，有且仅有一个 [i,j,k][i,j,k][i,j,k] 的排列 PPP，使得 P1<P2<P3P_1 \lt P_2\lt P_3P1 <P2 <P3 。 考虑枚举 jjj，那么 iii 和 kkk 可以独立选择。 满足条件的 iii 的数量是 AAA 中数值小于 AjA_jAj 的元素个数； 满足条件的 kkk 的数量是 AAA 中数值大于 AjA_jAj 的元素个数。 因此，只要准备一个数组 cnt，令 cnt[x] 为 AAA 中小于等于 xxx 的数量，便可以很容易地计算出满足条件的 iii 和 kkk 的数量。 AC代码 C++ AC代码： Python AC代码： 复杂度分析 统计所有数字出现的次数，使用前缀和处理 cnt 数组，最终枚举 jjj 统计答案，时间复杂度为 O(N+max⁡A)\mathrm{O}(N + \max{A})O(N+maxA)。