CCF 202112-2！

1225 字
4 分钟

序列查询新解

主要思想分析

直接遍历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 #include #include #include using namespace std; long long r,n,N,f = 0; vector 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,ri,i)+res(ri+1,rg,i); //相等点为 r*i } } cout << error; return 0; }