序列查询新解

https://www.acwing.com/problem/content/4284/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int a[N];
int R;

LL get(int l, int r)  // 求g[l] + g[l + 1] + ... + g[r]
{
    if (l / R == r / R) return (LL)(r - l + 1) * (l / R);
    int a = l / R + 1, b = r / R - 1;
    LL res = (a + b) * (LL)(b - a + 1) / 2 * R;  // 中间部分
    res += (a - 1) * (LL)(a * R - l);  // 左边界
    res += (b + 1) * (LL)(r - (b * R + R) + 1);  // 右边界
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    a[n + 1] = m;
    R = m / (n + 1);

    LL res = 0;
    for (int i = 0; i <= n; i ++ )
    {
        int l = a[i], r = a[i + 1] - 1;
        int x = l / R, y = r / R;
        if (y <= i || x >= i)
        {
            res += abs((LL)i * (r - l + 1) - get(l, r));
        }
        else
        {
            int mid = i * R;
            res += abs((LL)i * (mid - l + 1) - get(l, mid));  // 左半边
            res += abs((LL)i * (r - mid) - get(mid + 1, r));  // 右半边
        }
    }

    printf("%lld\n", res);
    return 0;
}