不正经题解 - 前缀和优化计数

容易想到的方法是 $O(n^3)$ 暴力枚举，但是看数据范围直接再见。
比较容易想到的方法是 $O(n^2)$ 组合计数，但是看数据范围也可以再见。
不是很容易想到的方法之一是二分优化组合计数，时间复杂度是 $O(n\log n)$，可以通过。
不是很容易想到的方法之二是前缀和优化组合计数，时间复杂度是 $O(n)$，可以通过。
因为标题是前缀和优化计数，所以这里讲第四种。

首先想 $O(n^2)$ 的：我们先用一个桶 $B$ 进行计数。然后，我们枚举 $j$。这个时候我们可以令 $i$ 的选择数量就是严格小于 $j$ 的数的数量，$k$ 的选择数量就是严格大于 $j$ 的数的数量。原因很简单，原文的限制条件令每个三元组只被选到一次，我们改变的限制条件同样令每个三元组只被选到一次，所以两者本质相同。根据组合数学的乘法原理，答案即为：

$$\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)$$

（在此 $\infty$ 取 $2\times 10^5$ 即可。）

显然括号里的两团式子可以用前缀和 $O(1)$ 搞掉。代码就很简单了。

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

#define PRI(x) printf(#x":%d\n",x);

int a[200005],b[200005],s[200005];

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		b[a[i]]++;
	}
	for(int i=1;i<=200000;i++) s[i]=s[i-1]+b[i];
	long long ans=0;
	for(int i=1;i<=200000;i++){
		ans+=(long long)b[i]*s[i-1]*(s[200000]-s[i]);
	}
	printf("%lld",ans);
	
	return 0;
}

双倍经验：ABC252D