[CF] D. Almost Difference - Educational Codeforces Round 34 (Rated for Div. 2)

Solutions Codeforces 算贡献 int128 2200 Med-

Lastmod: 2025-02-01 周六 23:50:45

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;
}

Prev: [CF] C. Boxes Packing - Educational Codeforces Round 34 (Rated for Div. 2)
Next: [CF] E. Swapping Characters - Educational Codeforces Round 34 (Rated for Div. 2)

Gitalking ...

	#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;
	}