自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 22:55:11，当前版本为作者最后更新于2024-02-09 20:45:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

每种数只会出现 $\le 3$ 次，而且只有 $2$ 次或 $3$ 次会产生贡献：

• $2$ 次：若两个数在分界线的两边则产生贡献；
• $3$ 次：若三个数为 $1|2$ 或 $2|1$ 则产生贡献；

则问题可以转化成：

• 有若干个数的 pair $x,y$，如果每次操作后查询，这两个数当前在分界线的两边，则会产生 $v$ 的贡献。
• 对于 $2$ 次的情况，则 $(x,y)$ 产生 $1$ 的贡献；对于 $3$ 次的情况，则 $(x,y),(y,z),(x,z)$ 各产生 $0.5$ 的贡献。

套用 TB5 分治，则每个分治节点只需要处理 $O(len^2)$ 个信息，即每两个等价类之间的贡献。总复杂度 $O(n+m\sqrt n)$。