#CS1144. 工资查询

工资查询

题目背景

翻译自 CSES-1144 题。

题目描述

公司有 n 名员工，每个员工有一定的工资。你的任务是跟踪员工的工资并处理查询。

输入格式

第一行包含两个整数 n 和 q：分别表示员工的数量和查询的数量。员工的编号为 1,2,…,n1,2,…,n1,2,…,n。

第二行包含 n 个整数 p1,p2,…,pnp_1,p_2,…,p_np1​,p2​,…,pn​：表示每个员工的工资。

接下来有 q 行描述查询。每一行有以下两种格式之一：

• ! k x：将第 k 位员工的工资修改为 x。

• ? a b：统计工资在区间 [a,b][a, b][a,b] 之间的员工数量。

输出格式

对于每个 ? 查询，输出区间 [a,b][a, b][a,b] 内工资的员工数量。

样例

5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3

3
2

说明/提示

$1 \leq n,q \leq 2 \cdot 10^5$

1≤pi≤1091 \leq p_i \leq 10^91≤pi​≤109；

$1 \leq k \leq n$

$1 \leq x \leq 10^9$

$1 \leq a,b \leq 10^9$