← 返回题目列表

AtCoder · ndpc2026_g

G. 嘴

中文机器翻译题面 查看原题

分数: 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