5475. 比萨店查询（Pizzeria Queries）
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 一条街上有 $n$ 栋建筑物，编号为 $1, 2, \dots, n$。每栋建筑物里都有一家比萨店和一个公寓。 在第 $k$ 栋建筑中，比萨的价格为 $p_k$。如果你在第 $b$ 栋建筑中向第 $a$ 栋建筑的比萨店订购一份比萨，其配送到家的总价格为 $p_a + |a - b|$。 你需要处理两种类型的查询： 1. 第 $k$ 栋建筑的比萨价格 $p_k$ 修改为 $x$。 2. 你现在在第 $k$ 栋建筑，想要订购一份比萨。请问你能获得的最便宜的总价格是多少？ ## 输入格式 第一行两个整数 $n$ 和 $q$，分别表示建筑物数量和查询数量。 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，表示各建筑比萨的初始价格。 接下来 $q$ 行描述查询，格式为“1 $k$ $x$” 或 “2 $k$”。 ## 输出格式 对于每个类型 2 的查询，输出对应的最低总价格。 ## 输入输出样例 ### 输入 #1 ``` 6 3 8 6 4 5 7 5 2 2 1 5 1 2 2 ``` ### 输出 #1 ``` 5 4 ``` ## 说明/提示 ### 数据规模与约定 - $1 \le n, q \le 2 \cdot 10^5$ - $1 \le p_i, x \le 10^9$ - $1 \le k \le n$