序列查询

题目描述

是一个由 n+1 个 [0,N) 范围内整数组成的序列，满足（这个定义中蕴含了 n 一定小于 N。）
基于序列 A，对于 [0,N) 范围内任意的整数 x，
查询 定义为：序列 A 中小于等于 x 的整数里最大的数的下标。具体来说有以下两种情况：

2.
即是



对于给定的序列 A，试计算。

v=list(map(int,input().split()))
n,m=v[0],v[1]
a =list(map(int,input().split()))
sum =0
for i in range(len(a)-1):
    if a[i]<m and a[i+1]>m:
        sum+=(m-a[i])*(i+1)
        break
    else:sum+=(a[i+1]-a[i])*(i+1) 
if m>a[-1]:
    sum+=(m-a[-1])*n
print(sum)

首先定义了比例系数 ，其中 ⌊ ⌋ 表示下取整，即 r 等于 N 除以 n+1 的商。进一步地，用表示自己估算出的 f(x) 的大小，这里同样使用了下取整来保证 g(x) 是一个整数。
显然，对于任意的询问 越接近则说明小 P 的估计越准确，后续进行线性查找的时间开销也越小。因此，小 P 用两者差的绝对值来表示处理询问 x 时的误差。
为了整体评估小 P 同学提出的方法在序列 A 上的表现，试计算：

优化求和

想法:

不是从0遍历到，而是遍历序列A的长度，即是，需要

• 把相同的合并计算
• 对绝对值进行拆开讨论
• 合并计算

  如何分开计算

  对于有相同的，

  但是如何计算？定义前缀和：

  ，假如我们可以很快地计算出
  于是就可以在分开计算：
  当 ：
  
  当:
  
  当绝对值的变号发生在区间内部时，即是
  边界点是 ,
  
  
  进一步可以优化：只需要把判断移到内部，替换掉求和的边界以

  for  i in range(len(a)-1):
    x = r*i
    if (x>a[i]):
        real = min(a[i+1],x)
        sum += (real-a[i])*i-(h(real-1)-h(a[i]-1))
    if(x<a[i+1]):
        real =max(a[i],x)
        sum += h(a[i + 1] - 1) - h(real - 1) - (a[i + 1] - real) * i

  如何计算?
  例子：取x=7,r=3

可以看作有r个独立的等差数列{0，1},与余下不能分配到r个构成等差数列的数
等差数列，首项为0，末项为，有项
剩下的数均为，有个

def h(x):
    t = (x+1)//r
    return r*(t-1)*t/2+t*((x+1)%r)

一一对应相

v=list(map(int,input().split()))
n,m=v[0],v[1]
a =list(map(int,input().split()))
max_num =a[-1]
b=[0]*a[0]
for index in range(n-1):
    b+=[index+1]*(a[index+1]-a[index])
b+=[n]
sum =0
r = m//(n+1)
if m>n:
    for i in range(max_num+1):
        sum+=abs(i//r-b[i])
    for j in range(max_num+1,m):
        sum+=abs(j//r-b[-1])
else:
    for i in range(m):
        sum+=abs(i//r-b[i])
print(sum)

v=list(map(int,input().split()))
n,m=v[0],v[1]
a =list(map(int,input().split()))
max_num =a[-1]
b=[0]*a[0]
for index in range(n-1):
    b+=[index+1]*(a[index+1]-a[index])
b+=[n]
sum =0
r = m//(n+1)
if m>n:
    for i in range(max_num+1):
        sum+=abs(i//r-b[i])
    for j in range(max_num+1,m):
        sum+=abs(j//r-b[-1])
else:
    for i in range(m):
        sum+=abs(i//r-b[i])
print(sum)