Oiclass PUJI 971 题解

数学题！！！

为了方便化简式子，我们首先简单的将

\[ d(x, y)=y-x \]

替代

\[ d(x, y)=\left\{ \begin{array}{l} 0\ \ (|x - y|\le1)\\ y - x\ \ (|x - y| > 1) \end{array} \right. \]

那么就可以令 \(n = 4\) 将原式（

\[ \sum^{n}_{i = 1}\sum_{j = i +1}^n d(a_j, a_i) \]

）转换为这样的一个表格：

\(i = 1\)	\(a_2 - a_1\)	\(a_3 - a_1\)	\(a_4 - a_1\)
\(i = 2\)	\(a_3 - a_2\)	\(a_4 - a_2\)
\(i = 3\)	\(a_4 - a_3\)

如果我们把它加上一行，得到这样一个表格：

	\(j = 3\)	\(j = 2\)	\(j = 1\)
\(i = 1\)	\(a_2 - a_1\)	\(a_3 - a_1\)	\(a_4 - a_1\)
\(i = 2\)	\(a_3 - a_2\)	\(a_4 - a_2\)
\(i = 3\)	\(a_4 - a_3\)

然后我们写出一条按列求和的算式：

\[ \sum_{j = 1}^{n} (a_{j +1} - a_j) + (a_{j + 2} - a_j) + ... + (a_{n - 1} - a_j) + (a_{n} - a_j) \]

\[ 令\ s_i = \sum_{j = 1}^{i} a_j\ \ (即\ s\ 是\ a\ 的前缀和) \]

我们根据表中可以看出的规律将符号为正的 \(a_j\) 项放到一起，我们会发现他们的和是 \(s_n - s_{n - j} - s_j\)

同理，我们把符号为负的项求和，得到 \(s_j\)

然后我们就会得到每一列的和就是

\[ s_{n} - s_{n - j} - s_j \]

我们将每一列求和，得到式子：

\[ \sum_{j = 1}^n s_{n} - s_{n - j} - s_j \]

这时候，我们已经得到的一个部分解，现在让我们考虑题目中给出的情况，即：

\[ d(x, y)=\left\{ \begin{array}{l} 0\ \ (|x - y|\le1)\\ y - x\ \ (|x - y| > 1) \end{array} \right. \]

我们就会发现，如果 \(d(x, y)=y - x\) ，那么 \(d(x, x - 1) = -1\) 对于我们题目中的函数 \(d(x, y)\) 来说，这一个值很显然小了 \(1\)，所以我们需要统计这种情况，然后在答案中补偿进去，同理，当 \(d(x, x +1) = 1\) 时，我们多计算了 \(1\) ，所以我们需要在最终的答案里面减去这个 \(1\)。

那么我们如何知道这个 \(x +1\) 或者 \(x - 1\) 的个数呢？很显然，我们可以使用一个桶数组 $ cnt $来解决，我们只需要在计算时减去 \(cnt_{a_j - 1}\) 再加上 \(cnt_{a_j + 1}\) 即可，注意要 \(cnt_{a_i} += 1\)

好了，那么我们的思路就是这样，下面时 ctjers 的最爱，代码：

#include <iostream>

#define int long long

using namespace std;

int n, ans, a[100009], s[100009], cnt[100009];

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        ans += s[n] - s[n - i] - s[i];
        ans -= cnt[a[i] - 1];
        ans += cnt[a[i] + 1];
        cnt[a[i]] += 1;
    }
    cout << ans;
}