蓝桥杯 python 小明的彩灯 差分前缀和

蓝桥杯 python 小明的彩灯 差分前缀和

2022.04.07
愿一切的付出都会有回报。

小明的彩灯

步骤：

• 1.构建初始差分数组b（遍历数组a，对数组b在i位置插a[i]）
• 2.根据题意修改差分数组
• 3.利用修改后的差分数组重新计算前缀和

代码

n, q = map(int,input().split())
def insert1(b,l,r,c):
    b[l] += c
    b[r + 1] -= c
a = [0] * (n + 10) # 原数组
b = [0] * (n + 10) # 构建差分数组
nums = list(map(int, input().split())) 
for index,val in enumerate(nums):
    a[index + 1] = val
# 构建初始差分数组b[]
for i in range(1, n + 1):
    insert1(b, i, i, a[i])
# 根据题意修改差分数组
while q:
    q -= 1
    l, r, c = map(int, input().split())
    insert1(b, l, r, c)
for i in range(1, n + 1):
    b[i] += b[i - 1]
for i in range(1, n + 1):
    print(b[i] if b[i] > 0 else 0,end = ' ') # 如果为负数，输出0就可以了

一阶差分模板

# 核心
def insert(b, l, r, c):
    b[l] += c
    b[r+1] -= c


if __name__ == "__main__":
    n, m = map(int, input().split())
    a = [0] * (n + 10)  # 原数组
    b = [0] * (n + 10)  # 差分数组
    nums = list(map(int, input().split()))
    for index, val in enumerate(nums):
        a[index+1] = val
        
    # 构建初始差分数组b[]
    for i in range(1, n+1):
        insert(b, i, i, a[i])
    
    # 根据题意修改差分数组
    while m > 0:
        m -= 1
        l, r, c = map(int, input().split())
        insert(b, l, r, c)
        
    # 利用修改后的差分数组重新计算前缀和
    for i in range(1, n+1):
        b[i] += b[i-1]
    for i in range(1, n+1):
        print(b[i], end=" ")

n, q = map(int, input().split())
a = [0] * (n + 10) # 原数组
b = [0] * (n + 10) # 构建差分数组
nums = list(map(int, input().split())) 
for index,val in enumerate(nums):
    b[index + 1] = val
while q:
    q -= 1
    l, r, c = map(int, input().split())
    a[l] += c
    a[r + 1] -= c
for i in range(1, n + 1):
    a[i] += a[i - 1]
for i in range(1, n + 1):
    print(max(a[i] + b[i], 0), end = ' ')