P17422 [ICPC 2018 Xuzhou R] Rikka with Data Structures

众所周知，Rikka 并不擅长数据结构。Yuta 对此感到担忧，于是他给 Rikka 布置了一些数据结构相关的练习任务。以下是其中之一： Yuta 有一个包含 $n$ 个数的数组 $A$，记为 $A[1], A[2], \cdots, A[n]$。随后他在该数组上执行 $m$ 次操作。操作共有三种类型： * $\text{1 l r k}$：对于每个满足 $i \in [l, r]$ 的下标 $i$，将 $A[i]$ 的值改为 $(A[i] + k)$； * $\text{2 l r k}$：对于每个满足 $i \in [l, r]$ 的下标 $i$，将 $A[i]$ 的值改为 $k$； * $\text{3 l r x}$：Yuta 想让 Rikka 统计满足 $l \le y \le r$ 且 $\max \lbrace A[\min \lbrace x, y \rbrace ], A[\min \lbrace x, y \rbrace +1], \cdots, A[\max \lbrace x, y \rbrace ] \rbrace = \max \lbrace A[x], A[y] \rbrace$ 的不同下标 $y$ 的数量。 这对 Rikka 来说太难了。你能帮帮她吗？

输入包含多组测试数据，第一行包含一个整数 $T$（$1 \le T \le 200$），表示测试数据的组数。 对于每组测试数据，第一行包含两个整数 $n$（$1 \le n \le 10^5$）和 $m$（$1 \le m \le 10^5$）。 第二行包含 $n$ 个整数 $A[1], A[2], \cdots, A[n]$（$1 \le A[i] \le 10^9$）。 接下来 $m$ 行，每行描述一个操作，包含四个如上所述的整数，且满足 $1 \le l \le r \le n$，$1 \le k \le 10^9$，$1 \le x \le n$。 输入保证至多有 $10$ 组测试数据满足 $n > 10^3$ 或 $m > 10^3$。

对于每个类型为 $3$ 的询问操作，输出一行一个整数，表示该询问的答案。

翻译由 DeepSeek V4 Pro 完成