T546814 「2025 YAC Round 1」姆Q的魔导书

「2025 YAC Round 1」E 题  图片来源：[pixiv_id=119492596](https://www.pixiv.net/artworks/119492596)

在红魔馆大图书馆，帕秋莉有 $n$ 本有关“贤者之石”的魔导书。 每本魔导书有一个卷次 $a_i$。这 $n$ 本书在某个书架上的排成一排形如 $a_1,a_2,\ldots, a_n$。且可能存在相同卷次的书。 帕秋莉有 $q$ 次 提问 或 加书 的操作： - `1 l r x`：询问区间 $a_l, a_{l+1}, \ldots, a_r$ 中卷次为 $x$ 的魔导书的数量； - `2 x`：将 $1$ 本卷次为 $x$ 的魔导书加入到这排书的末尾。

第一行输入两个正整数 $n, q$（$1 \le n \le 2 \times 10^5, 1 \le q \le 10^5$），分别表示 魔导书的数量 和 操作次数。 第二行输入 $n$ 个整数 $a_1,a_2, \ldots, a_n$（$1 \le a_i \le 10^9$，$i \in [1, n]$），表示每本魔导书的卷次。 接下来的 $q$ 行，每行输入一个如题意所示的操作： - 对于操作 `1 l r x`，保证 $1 \le l \le r \le |a|, 1 \le x \le 10^9$，其中 $|a|$ 表示此时魔导书的数量。 - 对于操作 `2 x`，保证 $1 \le x \le 10^9$。

对于每个提问操作 `1 l r x`，输出一行一个整数表示答案。

#### 样例解释 第一次询问区间 $a_1, a_2, a_3, a_4$ 中 $3$ 的个数，答案为 $2$。 第二次操作将一个 $2$ 插入到序列的末尾。序列变为 $1,2,3,3,3,2$。 最后一次询问 $a_2, a_3, a_4, a_5, a_6$ 中 $2$ 的个数，答案为 $2$。