[Contest #7]最简单的题

给你一个长为 $n$ 的序列，定义区间 $[l,r]$ 的子区间为所有形如 $[l',r']$ 的区间，满足 $l',r'$ 为整数，且 $l \le l' \le r' \le r$。

有 $m$ 次操作：

$1$ $x$ $y$：将 $x$ 位置的值修改为 $y$

$2$ $l$ $r$ $x$：查询区间$[l,r]$中有多少子区间的最大值小于或等于 $x$

第一行有两个整数 $n,m$，第二行有 $n$ 个整数表示这个序列。

接下来 $m$ 行，每行形如 $1$ $x$ $y$ 或者 $2$ $l$ $r$ $x$ 表示每次操作。

数据满足 $n , m \le 3 \times 10^5$， $1 \le l \le r \le n$，$1 \le x, y \le n$，序列中每个元素都在 $[1,n]$ 中，所有数均为整数。

对于每个 $2$ 操作，输出一行一个数表示答案。

6 6
1 1 4 5 1 4
1 1 4
2 1 4 2
2 1 1 4
2 1 5 4
1 5 4 
2 3 3 3

样例解释：

最开始序列是 $1$ $1$ $4$ $5$ $1$ $4$。

第一次操作之后，序列变为了$4$ $1$ $4$ $5$ $1$ $4$。

第二次操作查询区间$[1,4]$中有多少子区间 $max\le 2$，得到 $1$。

第三次操作查询区间$[1,1]$中有多少子区间 $max\le 4$，得到 $1$。

第四次操作查询区间$[1,5]$中有多少子区间 $max\le 4$，得到 $7$。

第五次操作之后，序列变为了$4$ $1$ $4$ $5$ $4$ $4$。

第六次操作查询区间 $[3,3]$ 中有多少子区间 $max\le3$，得到 $0$。

C1173 [Contest #7]最简单的题