Pizzeria Queries

题目描述

街上有 $n$ $$座建筑，编号为 1,2,$\dots$,$n$。每座建筑都有一家披萨店和一间公寓。 第 $k$ 座建筑的披萨价格为 $p_k$。如果你从建筑 $a$ 向建筑 $b$ 订披萨，其价格（含配送费）为 $p_a+|a-b|$。 你的任务是处理两类查询：

输入格式

第一行输入有两个整数 $n$ 和 $q$：建筑数量和查询数量。 第二行有 $n$ 个整数 $p_1,p_2,$$\dots$,$p_n$：每座建筑的初始披萨价格。 最后有 $q$ 行，每行描述一个查询。每行要么是 "1 k x"，要么是 "2 k"。

输出格式

对于每个类型为 2 的查询，输出答案。

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

5
4

提示

$1 \le n,q \le 2 \cdot 10^5$ $1 \le p_i, x \le 10^9$ $1 \le k \le n$

标签: CSES2206|区间查询

来源

CSES2206|区间查询