题解

题意翻译：给定一个数列 $A$，你可以选择两个正整数 $l,r$，并将 $A_l,A_{l+1},...,A_{r-1},A_r$ 都变为它们的平均数，求操作后 $A$ 数列的种数。

我们正着求种数太复杂了，考虑拿总数（即 $N\times(N+1)\div 2$）减去重复的情况数。

重复情况分为以下两种：

1. $A_j,A_{j+1},...,A_{i-2},A_{i-1}$ 的平均数恰好为 $A_i$。
2. $A_{i+1},A_{i+2},...,A_{j-1},A_{j}$ 的平均数恰好为 $A_i$。

情况 2 我想不出来怎么弄，所以就把 $A$ 数列反转一下，求两次情况 1，最后加回重复减的。

注意到所有 $A_i$ 均为正整数，所以如果情况重复，那么平均数也必定是正整数，且在 $[1,30]$ 内。

我们可以创建数组 $pre$，使 $pre[i][j]=\sum_{k=1}^j (A_k-i)$，这样如果 $pre[i][j]=pre[i][k]$，就说明 $A_j,A_{j+1},A_{j+2},...,A_{k-1},A_k$ 的平均数为 $i$。

于是操作 1 记录的就是如下的式子：

$$\sum_{i=1}^N \sum_{j=0}^{i-1} (pre[A_i][i]=pre[A_i][j])$$

接着我们想想这样会多减多少种情况。

显然，如果两个正整数 $i,j$ 满足 $A_i=A_j$ 且 $A_{i+1},A_{i+2},..A_{j-2},A_{j-1}$ 的平均数也恰好为 $A_i$，则这种情况会被减两次，需要加回来。

所以要加回来的总情况数就是：

$$\sum_{i=1}^N\sum_{j=1}^{i-1} (A_i=A_j\space且 \space pre[A_i][i]=pre[A_i][j])$$

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
#define int long long 
using namespace std;
int pre[35][100005];
int a[100005];
int n, ans;
void solve(){
	memset(pre, 0, sizeof(pre));
	for(int i = 1; i <= 30; i++){
		for(int j = 1; j <= n; j++){
			pre[i][j] = pre[i][j - 1] + a[j] - i;
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < i - 1; j++){
			if(pre[a[i]][i] == pre[a[i]][j]){
				ans--;
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	ans = n * (n - 1) / 2;
	for(int i = 1; i <= n; i++) cin >> a[i];
	solve();//正着统计 
	
	reverse(a + 1, a + n + 1);
	solve();//反着统计 
	
	reverse(a + 1, a + n + 1);
	//容斥，加回减了两次的状态 
	memset(pre, 0, sizeof(pre));
	for(int i = 1; i <= 30; i++){
		for(int j = 1; j <= n; j++){
			pre[i][j] = pre[i][j - 1] + a[j] - i;
		}
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j < i; j++){
			if(a[i] == a[j] && pre[a[i]][i] == pre[a[i]][j]){
				ans++;
			}
		}
	}
	
	ans++;
	cout << ans;

	return 0;
}

时间复杂度 $O(N\times A_i+N^2)$。

这篇代码可以通过离散化（排序聚集相等元素）优化成 $O(N\log N\times A_i)$，请读者自行完成。