分数: 4 点
问题陈述
给你一个整数序列 A = (A_1, A_2, \dots, A_N) 长度 N.
流程 Q 查询。在每个查询中,您都会得到一个整数 i (1 \leq i \leq N) 和一个非负整数 v。更新 A_i to v,然后解决以下问题。 (更新是永久性的。)
有 N 人们站在数轴上的位置 1 to N,每个人都张着嘴。人 i 位于位置 i。每个人都有一个参数,叫做 饥饿,以及人的饥饿 i is A_i.
你有无限数量的糖果。您决定执行以下一系列操作一次来喂它们:
- 首先,选择一个整数 x 这样 1 \leq x \leq N,并站在位置 x.
- 然后,执行以下操作任意次数(可能为零):
- 让您当前的位置为 y。移动到位置 y-1, y,或 y+1。但是,您无法移动到没有人站立的位置。
- 将一颗糖果扔到你当前位置的人的嘴里。
完成所有操作后,让 B_i 是给予人的糖果数量 i。找到最小可能值 \displaystyle \sum_{i=1}^N \vert A_i - B_i \vert.
约束
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 0 \leq A_i \leq 10^9
- 1 \leq i \leq N
- 0 \leq v \leq 10^9
- 所有输入值均为整数
部分分数
此题得分不全。
- 如果您使用以下方法求解数据集 Q \leq 10,你会得到 2 点。
输入
输入由标准输入给出,格式如下:
N Q
A_1 A_2 \dots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询均按以下格式给出:
i v
输出
打印 Q 行。对于 i第行,输出答案 i-第一个查询。
示例输入 1
4 3 1 3 0 2 2 0 1 3 3 5
示例输出 1
1 2 1
考虑处理第一个查询。您需要解决以下问题: A = (1,0,0,2).
在这种情况下,以下操作实现的值是 1,这是最佳的:
- 选择 x=3 并站在位置 3.
- 移至位置 4 并给某人一颗糖果 4.
- 留在原地 再次 4 并给某人另一颗糖果 4.
- 结束操作。由此产生的 B 变为 (0,0,0,2).
示例输入 2
10 9 1 0 0 0 0 0 4 0 0 2 3 2 7 0 1 9 6 4 1 1 10 0 1 0 6 0 5 7
示例输出 2
5 3 3 5 5 3 2 0 1