CSES2206 披萨店查询
#CS2206. 披萨店查询
披萨店查询
题目背景
翻译自 CSES-2206 题。
题目描述
街道上有 n 栋建筑，编号为 1,2,...,n1,2,...,n1,2,...,n。每栋建筑都有一个披萨店和一间公寓。
第 k 栋建筑的披萨价格为 pkp_kpk。如果你从建筑 a 订购披萨送到建筑 b，其价格（包括配送费用）为 pa+∣a−b∣p_a+∣a−b∣pa+∣a−b∣，其中 ∣a−b∣∣a−b∣∣a−b∣ 是建筑 a 到建筑 b 的距离。
你的任务是处理两种类型的查询：
-
更新建筑 k 的披萨价格为 x。
-
你在建筑 k 并想订购披萨，询问最低的披萨价格是多少。
输入格式
第一行包含两个整数 n 和 q：分别表示建筑的数量和查询的数量。
第二行包含 n 个整数 p1,p2,…,pnp_1,p_2,…,p_np1,p2,…,pn：表示每栋建筑初始的披萨价格。
接下来有 q 行描述查询。每一行是以下两种之一：
-
1 k x：将建筑 k 的披萨价格更新为 x。
-
2 k：你在建筑 k，询问从建筑 k 订购披萨的最低价格。
输出格式
对于每个查询类型为 2 的查询，输出一个整数，即从建筑 k 订购披萨的最低价格。
样例
6 3
8 6 4 5 7 5
2 2
1 5 1
2 2
5
4
说明/提示
1≤pi,x≤1091 \leq p_i,x \leq 10^91≤pi,x≤109；