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

板块: Range Queries

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一家公司拥有 $n$ 名薪资各不相同的员工。你的任务是跟踪这些薪资并处理查询。

输入

第一行输入包含两个整数 $n$ 和 $q$：分别表示员工数量和查询数量。员工编号为 $1,2,\ldots,n$。

下一行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$：每名员工当前的薪资。

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

• ! $k$ $x$：将员工 $k$ 的薪资改为 $x$
• ? $a$ $b$：统计薪资在 $a \ldots b$ 之间的员工人数

输出

对每个 ? 查询输出其答案。

数据范围

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

样例输入

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

样例输出

3
2