CCF 202112-2！

序列查询新解

主要思想分析

直接遍历N虽然简单但一定会超时。
尝试以遍历n，在每两个n之间，f(i)相等。我们把区间左端点记为lf，右端点记为rg，在两个n之间，可能有三种情况。

1. g(lf) >= fi; //在此区间中g(i)全部大于fi
2. g(rg) <= fi; //在此区间中g(i)全部小于fi
3. 在此区间中g(i)在
   1. i <=r*fi
      g(i) <= i;小于i
   2. i > r*fi
      g(i) > i;大于i

对于1，2两种情况，error += abs(gi-fi);即等于，g(i)的和 - fi的合

对于数列g(i) 的分析

由上述分许，我们需要计算g(i)的和，我们记为和数列s(i)
数列g(i)的以r为间隔的项组合在一起可视为一个等差数列，对于数列

0	0	0	1	1	1	2	2	2	3	3	3
0	1	2	3	4	5	6	7	8	9	10	11

当我们计算s(10)时，g(10) = 3，我们可知从0到2的数列都有完整的r个，所以`s(8) = r * (0->(i-r+1)/r)【等差数列求和】+ ((i+1)%r)*(i/r)`; 注意：下标从0开始计算，所以有i+1个数字。 ## 对于数列fi求和 fi求和即等于`fi * (rg- lf + 1)`

#include<iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
long long r,n,N,f = 0;
vector<long long > arr(1,0);

long long  s(int i) {
    long long  tmp = (i-r+1)/r;
    long long tmp1 = ((i+1)%r)*(i/r);
    long long tmp2 = ((tmp+1)*tmp/2)*r;
    return tmp2+tmp1;
}
long long g(long long x) {
    return x/r;
}
long long res(long long lf,long long rg,long long fi) {
    return abs(s(rg)-s(lf-1)-fi*(rg-lf+1));
}
int main() {
    cin >>n >> N;
    arr.resize(n+1);
    r = N/(n+1);
    long long error = 0;
    for(int i = 0;i<= n;i++) {
        if(i < n)
            cin >> arr[i+1];
        else
            arr.push_back(N);
        long long lf = arr[i],rg = arr[i+1]-1;  //区间保留左侧端点，去除右侧端点。与题目[0,N）契合
        if(g(lf) >= i || g(rg) <= i ) {
            error+=res(lf,rg,i);
        }
        else {
            error+=res(lf,r*i,i)+res(r*i+1,rg,i); //相等点为 r*i
        }
    }
    cout << error;
    return 0;
}