题意解读：

有一个长度为nnn的序列AAA，序列AAA中的所有元素的取值在[0,N−1][0,N-1][0,N−1]中，f(x)f(x)f(x)代表序列AAA中小于等于xxx的最大整数的下标（注意看清题目），定义g(x)g(x)g(x)为x/rx/rx/r（下取整），其中r=N/(n+1)r=N/(n+1)r=N/(n+1)（下取整），求∑i=0N−1∣f(i)−g(i)∣\sum_{i=0}^{N-1}{|f(i)-g(i)|}∑i=0N−1​∣f(i)−g(i)∣，也就是估计值与真实值的误差和。

分析：

• 此题的NNN给到了1e91e91e9的范围，所以我们遍历NNN的话一定会超时，所以要考虑其他办法，此处我的做法是枚举n。

• 分析这个误差和，我们可以看到它带着绝对值，如果我们把绝对值拆开，那么我们就可以把∑i=0N−1∣f(i)−g(i)∣\sum_{i=0}^{N-1}{|f(i)-g(i)|}∑i=0N−1​∣f(i)−g(i)∣转化成如∑i=0N−1f(i)−∑i=0N−1g(i)\sum_{i=0}^{N-1}{f(i)}-\sum_{i=0}^{N-1}{g(i)}∑i=0N−1​f(i)−∑i=0N−1​g(i)类似的形式，这样做的好处就在于我们可以使用O(1)O(1)O(1)的时间复杂度求出连加。

• 我们知道f(x)f(x)f(x)代表序列AAA中小于等于xxx的最大整数的下标，那么如果我们遍历序列AAA，对于A[i]A[i]A[i]我们可以推出，以iii为fff值的xxx的范围就是在[A(i),A(i+1)−1][A(i),A(i+1)-1][A(i),A(i+1)−1]之间，那么这样我们就可以很轻松的求出有关fff的区间和，通过一行代码：

  ll f = i * (right - left + 1)
  

• 找到了求fff区间和的简便方法之后，我们就开始讨论求ggg的区间和的方法。我们知道g(x)g(x)g(x)=x/rx/rx/r（下取整），下取整赋予了它一个非常重要的性质，当x

  ll sigma_g(int x) {
  x++;
  ll groups = x / r;
  ll delta = x % r;
  ll sum = groups * (groups - 1) / 2 * r + delta * (groups);
  return sum;
  }
  

  此函数的功能是求g(0)+g(1)+...+g(x)g(0)+g(1)+...+g(x)g(0)+g(1)+...+g(x)的值，根据刚刚发现的那条性质，我们把这个特殊的等差数列先分个组，看有多少元素是可以通过等差数列求和再与rrr相乘直接得出，剩下的尾数单独加上。
  根据这个函数，如果我们需要求区间[i,j][i,j][i,j]的ggg值的和，我们就可以通过sigma_g(j)−sigma_g(i−1)sigma\_g(j)-sigma\_g(i-1)sigma_g(j)−sigma_g(i−1)来求，与前缀和的思想相同。

• 找到了求fff与ggg区间和的O(1)O(1)O(1)做法，我们这个时候就可以考虑怎么将绝对值符号拆开了。按照从小学到大的分类讨论法，讨论绝对值内部的正负性，当绝对值内部大于等于0时，绝对值可以直接拿掉；当绝对值内部小于0时，绝对值符号拿掉后还要将内部的值变为原来的相反数，可分为三种情况：

  • f>gf>gf>g由于我们枚举的是每一个A[i]A[i]A[i]，并且求出了以iii为fff值的xxx的范围是在[A(i),A(i+1)−1][A(i),A(i+1)-1][A(i),A(i+1)−1]之间，说明fff值在这个区间上全部都相同.因此如果f值有一个大于等于ggg的最大值，则整个区间上都有f>=gf>=gf>=g，也就是说绝对值符号可以直接去掉。
  • 反之，去掉绝对值后将绝对值内部取相反数
  • 当然也有一半fff大和一半ggg大的情况，根据g的区间递增性和f的区间不变性，我们只需要找到使f=gf=gf=g成立的那一个点，再分别按前面讨论的两种情况进行拆分绝对值即可，具体代码为：

    for (int i = 0; i <= n; i++) {//计算以a[i]为f值的x的左右边界ll lf, rt;if (i < n)lf = a[i], rt = a[i + 1] - 1;elself = a[i], rt = N - 1;//如果f值大于g(rt),证明f-g>=0,可以直接去掉绝对值if (rt / r <= i) {ll f = i * (rt - lf + 1), g = sigma_g(rt) - sigma_g(lf - 1);error += f - g;}else if (lf / r > i) {ll f = i * (rt - lf + 1), g = sigma_g(rt) - sigma_g(lf - 1);error += g - f;}else {//找到使g(x)==f(x)成立的x，此x一定存在因为g(x)是连续递增的ll j = lf;while (j <= rt) {if (j / r == i) {break;}j++;}ll f1 = (j - lf + 1) * i, f2 = (rt - j) * i;ll g1 = sigma_g(j) - sigma_g(lf - 1), g2 = sigma_g(rt) - sigma_g(j);error += f1 - g1 + g2 - f2;}}
    

完整代码：

#include 
#include 
#define ll long long
using namespace std;
const int maxn = 1e5 + 1;
int n, r, N, a[maxn];//求g(0)+...+g(x)的和
ll sigma_g(int x) {x++;ll groups = x / r;ll delta = x % r;ll sum = groups * (groups - 1) / 2 * r + delta * (groups);return sum;
}int main()
{cin >> n >> N;r = N / (n + 1);for (int i = 1; i <= n; i++) {cin >> a[i];}ll error = 0;for (int i = 0; i <= n; i++) {//计算以a[i]为f值的x的左右边界ll lf, rt;if (i < n)lf = a[i], rt = a[i + 1] - 1;elself = a[i], rt = N - 1;//如果f值大于g(rt),证明f-g>=0,可以直接去掉绝对值if (rt / r <= i) {ll f = i * (rt - lf + 1), g = sigma_g(rt) - sigma_g(lf - 1);error += f - g;}else if (lf / r > i) {ll f = i * (rt - lf + 1), g = sigma_g(rt) - sigma_g(lf - 1);error += g - f;}else {//找到使g(x)==f(x)成立的x，此x一定存在因为g(x)是连续递增的ll j = lf;while (j <= rt) {if (j / r == i) {break;}j++;}ll f1 = (j - lf + 1) * i, f2 = (rt - j) * i;ll g1 = sigma_g(j) - sigma_g(lf - 1), g2 = sigma_g(rt) - sigma_g(j);error += f1 - g1 + g2 - f2;}}cout << error;return 0;
}