[数据结构与算法]CSP 202112-2 序列查询新解

#include <iostream>
#include <vector>

using namespace std;

long long g(long long x, long long r) {
	long long t = x / r;
	return r * t * (t - 1) / 2 + t * (x % r);
}

long long f(long long x, long long y, long long r) {
	return g(y, r) - g(x, r);
}

int main()
{
	long long n, N;
	cin >> n >> N;
	vector<long long> a(n + 2);
	for (long long i = 1; i <= n; i++) {
		cin >> a[i];
	}
	a[n + 1] = N;
	long long ans = 0;
	long long r = N / (n + 1);
	for (long long i = 0; i <= n; i++) {
		if (i >= a[i + 1] / r) {
			ans += i * (a[i + 1] - a[i]) - f(a[i], a[i + 1], r);
		}
		else if (i <= a[i] / r) {
			ans += f(a[i], a[i + 1], r) - i * (a[i + 1] - a[i]);
		}
		else {
			ans += i * (i * r - a[i]) - f(a[i], i * r, r) + f((i + 1) * r, a[i + 1], r) - i * (a[i + 1] - (i + 1) * r);
		}
	}
	cout << ans;
}