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