链接: https://cses.fi/problemset/task/2206

板块: Range Queries

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一条街道上有 $n$ 栋建筑，编号为 $1,2,\dots,n$。每栋建筑都有一家披萨店和一套公寓。

建筑 $k$ 的披萨价格为 $p_k$。如果你从建筑 $a$ 向建筑 $b$ 订购披萨，包含配送费在内的价格为 $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 \le n,q \le 2 \cdot 10^5$ $1 \le p_i, x \le 10^9$ $1 \le k \le n$

样例输入

6 3
8 6 4 5 7 5
2 2
1 5 1
2 2

样例输出

5
4