https://codeforces.com/contest/903/problem/D
题目大意
给出 $n \ (\le 2 \times 10^5)$ 长的数组 $a$ 其中 $1 \le a_i \le 10^9$。定义函数 $d$ 如下
$$ d(x, y) = \left\{ \begin{align} y - x, \quad & |x - y| > 1, \\ 0, \quad & |x - y| \le 1 \end{align} \right. $$求
$$ \sum_i \sum_{j = i}^{n} d(a[i], a[j]) $$简要题解
注意到其实特殊的只有 $a[i] = a[j] \pm 1$ （等于虽然是 case 2，但其实和 case 1 算出来是一样的）。
于是我们只需要将三种情况分开处理，先把所有的都当做 case 1，算每个数作为 $i$ 和 $j$ 的贡献，之后再算对于 $case 2$ 多加或多减的部分即可。
分高是因为这题很恶心，会爆 long long！
比如前半全是 $1$，后半全是 $10^9$，这样有 $(10^9 - 1) \times 10^5 \times 10^5$ 这个量级（等差数列懒得算了。。。）
复杂度
$T$：$O(n \log n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
// using i128 = __int128;
using i128 = __int128_t;
std::istream &operator>>(std::istream &is, i128 &n) {
n = 0;
std::string s;
is >> s;
int len = s.length();
bool neg = (s[0] == '-');
for (int i = neg; i < len; i++) {
n = 10 * n + s[i] - '0';
}
if (neg) n = -n;
return is;
}
std::ostream &operator<<(std::ostream &os, i128 n) {
if (n == 0) return os << 0;
std::string s;
bool neg = false;
if (n < 0) { neg = true; n = -n; }
while (n > 0) {
s += '0' + n % 10;
n /= 10;
}
std::reverse(s.begin(), s.end());
if (neg) os << '-';
return os << s;
}
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int& i : a) cin >> i;
i128 ans = 0;
map<int, int> cnt;
for (int i = 0; i < n; i++) {
ans += 1LL * a[i] * i;
ans -= 1LL * a[i] * (n - i - 1);
// if a[i] is y
if (auto it = cnt.find(a[i] - 1); it != cnt.end()) {
ans -= it->second;
}
if (auto it = cnt.find(a[i] + 1); it != cnt.end()) {
ans += it->second;
}
cnt[a[i]]++;
}
cout << ans << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] E. Swapping Characters - Educational Codeforces Round 34 (Rated for Div. 2)