P14188 [ICPC 2024 Hangzhou R] Barkley III

猪国有 $n$ 只小猪。 它们都精通竞赛编程，第 $i$ 只小猪的 rating 为 $a_i$。 如果有 $k$ 只小猪 $p_1, p_2, \cdots, p_k$ 组队，那么队伍的 rating 为 $a_{p_1} \ \&\ a_{p_2}\ \&\ a_{p_3}\ \& \cdots \&\ a_{p_k}$，其中 $\&$ 表示按位与操作。 将要举办多场编程竞赛。 每场比赛，猪国只能派出一支队伍参赛。 对于第 $i$ 场比赛，只有编号在 $l_i$ 到 $r_i$ 之间（包含两端）的猪有空参加。 但由于经费短缺，必须从 $l_i$ 到 $r_i$ 之间恰好移除一只小猪，剩下的小猪才组队参赛。 猪头（教练）需要恰当选择不参赛的小猪，使得队伍 rating 最大。 但是，小猪们的 rating 可能会因为训练或参赛而变化。 作为猪头的好朋友，你的任务是维护小猪 rating 并处理以下 $q$ 个事件，事件有三种类型： - $1 \; l \; r \; x$：猪头把编号 $l$ 到 $r$（包含两端）的每只小猪的 rating 与 $x$ 执行按位与操作。即对于所有 $l \le i \le r$，$a_i$ 变为 $a_i\ \&\ x$。 - $2 \; s \; x$：将第 $s$ 只小猪的 rating 变为 $x$。 - $3 \; l \; r$：猪头询问编号在 $l$ 到 $r$（包含两端）的小猪组队，并移除其中恰好一只后，队伍 rating 的最大值是多少。

每个测试点仅有一组数据。 第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 10^6$，$1 \le q \le 10^6$），表示小猪的数量和事件数量。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$0 \le a_i < 2^{63}$），其中 $a_i$ 表示第 $i$ 只小猪的 rating。 接下来的 $q$ 行，每行描述一个事件。 第 $i$ 行首先包含一个整数 $op_i$（$op_i \in \{1, 2, 3\}$），表示第 $i$ 个事件的类型。 - 若 $op_i = 1$，则接下来有三个整数 $l, r, x$（$1 \le l \le r \le n$，$0 \le x < 2^{63}$）。 - 若 $op_i = 2$，则接下来有两个整数 $s, x$（$1 \le s \le n$，$0 \le x < 2^{63}$）。 - 若 $op_i = 3$，则接下来有两个整数 $l, r$（$1 \le l < r \le n$）。

对于每个第三类事件，输出一行一个整数，表示队伍可能得到的最大 rating。

由 ChatGPT 5 翻译