CCF202112-2 序列查询新解

#include 
using namespace std;

long long h(long long i, long long r) { //求g(i)的前缀和h(i)
    if (i < 0) return 0;
    else return r * ((i + 1) / r - 1) * ((i + 1) / r) / 2 + (i + 1) % r * (i / r);
}

long long cal(long long fi, long long lft, long long rgt, long long r) { //给定一个f(i),计算区间里的|g(i)-f(i)|之和,前提是g(i)全部小于等于或者全部大于等于f(i)
    return abs(h(rgt, r) - h(lft - 1, r) - fi * (rgt - lft + 1));
}

int main()
{
	long long n, N, t;
	cin >> n >> N;
	vector a = {0};
	for (int i = 0; i < n; ++i) {
		cin >> t;
		a.push_back(t);
	}
	a.push_back(N);
	long long r = N / (n + 1), ans = 0;
	for (long long fi = 0; fi <= n; ++fi) { //遍历每个f(i)
		long long lft = a[fi], rgt = a[fi + 1] - 1;
		if (lft / r >= fi || rgt / r <= fi) ans += cal(fi, lft, rgt, r); //如果区间内g(i)全部小于等于或者全部大于等于f(i),直接使用cal函数
		else ans += cal(fi, lft, r * fi, r) + cal(fi, r * fi + 1, rgt, r); //否则将区间分成两半，分别使用cal函数
	}
	cout << ans << endl;
	return 0;
}