题解 P10150 [Ynoi1999] TS-54

Rainbow_qwq · 2024-02-09 20:45:21 · 题解

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

则问题可以转化成：

• 有若干个数的 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)。