CF2182F2 Christmas Reindeer (hard version)

这是本题的高难度版本。两个版本的唯一区别是 $n$ 和 $m$ 的上限。在本版本中，$n \le 3 \cdot 10^5$ 且 $m \le 3 \cdot 10^5$。 你有一群 $n$ 头圣诞驯鹿。第 $i$ 头驯鹿的力量为 $2^{c_i}$。 一组 $k$ 头圣诞驯鹿的最大负载能力按照如下方式计算： - 首先将这些驯鹿的力量按不递增顺序排序。用 $c'_1, c'_2, \dots, c'_k$ 表示排序后的力量，其中 $c'_i \ge c'_{i+1}$； - 然后，这组驯鹿的最大负载能力等于 $c'_1 + \left\lfloor\frac{c'_2}{2}\right\rfloor + \left\lfloor\frac{c'_3}{4}\right\rfloor + \dots + \left\lfloor\frac{c'_k}{2^{k-1}}\right\rfloor$。 注意，有些驯鹿对组的最大负载能力的贡献可能为零。 你需要处理三种类型的操作： 1. 向队伍中增加一头力量为 $2^x$ 的驯鹿； 2. 从队伍中移除一头力量为 $2^x$ 的驯鹿； 3. 计算从队伍中任选若干头驯鹿（可能全部选上），使得所选组的最大负载能力不少于 $x$ 的选法数。 如果队伍中有多头驯鹿拥有相同的力量，它们被视为不同的个体。例如，若你有两头力量为 $1$ 的驯鹿，需要计算最大负载能力不少于 $1$ 的选法数，则有 $3$ 种选法：选第一头，选第二头，或者两头都选。

第一行包含两个整数 $n$ 和 $m$，表示初始驯鹿数量和操作数，$1 \le n, m \le 3 \cdot 10^5$。 第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$，$0 \le c_i \le 60$，表示第 $i$ 头驯鹿的力量为 $2^{c_i}$。 接下来 $m$ 行，每行描述一个操作之一，格式如下： - $1\ x$（$0 \le x \le 60$）：向队伍中增加一头力量为 $2^x$ 的驯鹿； - $2\ x$（$0 \le x \le 60$）：从队伍中移除一头力量为 $2^x$ 的驯鹿； - $3\ x$（$1 \le x \le 10^{18}$）：计算从队伍中任选若干头驯鹿（组，可以全部选上），使得所选组的最大负载能力不少于 $x$ 的选法数。 额外的输入约束：每当出现类型 2 的操作时，当前队伍里至少包含一头力量为 $2^x$ 的驯鹿。

每当遇到类型 3 的操作时，输出一个整数，表示满足条件的组数（组可全部选上）。由于答案可能很大，输出其对 $998244353$ 取模后的结果。

以第一个样例说明。初始有三头驯鹿，力量分别为 $4$、$2$ 和 $2$。 - 第一次操作，需要计算最大负载能力不少于 $5$ 的组数，共有三种组：$\{1, 2\}$（第 $1$ 和 $2$ 头），$\{1, 2, 3\}$ 以及 $\{1, 3\}$； - 第二次操作，需要计算最大负载能力不少于 $6$ 的组数。即使全部选上，最大负载能力 $4 + \left\lfloor\frac{2}{2}\right\rfloor + \left\lfloor\frac{2}{4}\right\rfloor = 5$，没有合法组； - 第三次操作，增加一头力量为 $4$ 的驯鹿，记为第 $4$ 头； - 第四次操作，能够满足条件的组为：$\{1, 4\}$，$\{1, 2, 4\}$，$\{1, 3, 4\}$，$\{1, 2, 3, 4\}$； - 第五次操作，此时有 $10$ 种方案； - 第六次操作，移除了一头力量为 $2$ 的驯鹿。假设是第 $2$ 头，现在还剩 $1, 3, 4$ 三头； - 第七次操作，需要计算最大负载能力不少于 $5$ 的组，有四种：$\{1, 3\}$、$\{1, 4\}$、$\{1, 3, 4\}$、$\{3, 4\}$。 由 ChatGPT 5 翻译