题解：P12608 骷髅打金服

王熙文 · 2025-06-06 12:21:32 · 题解

如果这题时限压缩到 1s 就真的是卡常神题了。最大点 566ms，记录一下卡常技巧。

思路

首先可以感受一下出现过的元素出现次数都相等是什么形态。将相同的数放到一行里列出一个矩形，比如：

1 1 1 1
2 2 2 2
3 3 3 3

可以很自然地想到每一列的值都是相等的。判定相等可以使用哈希，将每一个值 x 随机一个权值 qz_x，设每一个值的出现次数为 cnt_x，则判定条件即为 \sum_x qz_x\cdot cnt_x \bmod \sum_x qz_x = 0。

但是维护一个值是否出现是比较困难的。因为“出现过”这个信息不可减，所以无法使用前缀和作差的方式。但是这个信息是可加的，所以可以考虑分治。

但是分治后如果两边的数集不相同，还是没法做的，因为需要取并集的过程。那如果两边的数集不相同，有没有什么性质呢？

确实有。假设左边有一个在右边没出现的数 x，那么所有数的出现次数就都为 x 在左边出现的次数 cnt_x 了。进一步地，x 应当是众数，而且在左边出现的数在右边的出现次数就都确定了（对于 y 在右边出现的次数为 cnt_x-cnt_y）。

但是右边还可以有左边没出现的数。此时它也应当是右边的众数，而且出现次数与左边的众数应当相同。

这两种情况是无法合并的，因为右边的众数既可以出现在左边也可以不出现在左边。这就是剩下的情况还需要分三类的原因。大概的框架清楚了，接下来详细讨论一下四种情况。

没有只出现在一边的数：设 x 是左边的数，y 是右边的数，则 \sum_x qz_x=\sum_y qz_y 且 (\sum_x qz_x\cdot cnt_x+\sum_y qz_y\cdot cnt_y) \bmod \sum_x qz_x=0。
有只出现在左边的数，没有只出现在右边的数：设左边众数出现次数为 k，则 \sum_x qz_x \cdot (k-cnt_x)=\sum_x qz_y \cdot cnt_y。
有只出现在右边的数，没有只出现在左边的数：同理。
有只出现在左边的数和只出现在右边的数：设左边、右边众数出现次数分别为 kx,ky，则 kx=ky 且 \sum_x qz_x \cdot (kx-cnt_x)=\sum_y [cnt_x\ne ky] qz_y \cdot cnt_y。而且需要让两边众数的数集没有交。设左边众数在右边的最小位置为 wz，则右端点 r<wz。

前三种情况可以使用哈希维护，第四种情况可以在 wz 处记录下来查询并扫描线，也可以使用哈希维护。因此这道题做完了，复杂度为 \mathcal O(n \log n)。

若分治的区间长度 \le 100 跑 \mathcal O(n^2) 暴力。区间合法等价于一个区间的众数出现次数乘上不同的数的个数等于区间长度。
每个数的权值在 [0,9 \times 10^{12}) 内随机，这样既不会产生相同的元素，也可以让总和存储在 long long 里。
对于两个元素的储存，直接将它们异或起来而不是变成一个 __int128。
使用拉链法（而不是开放寻址法）存储哈希表。
将四个哈希表的询问预处理出来，使用一个哈希表重复四次而不是开四个哈希表。这样访问稍微连续一些。
哈希表桶的大小开 2^{18}。
每次分治的时候都将区间内的数离散化，这样可以有效降低值域，增加访问连续性。
使用 bfs 进行分治，这样可以让区间长度接近的询问放在一起做，同样增加访问连续性（优化效果存疑）。
计算 \sum_x qz_x\cdot cnt_x \bmod \sum_x qz_x 的时候（设两个值分别为 x,y），可以记录变量 z=\lfloor \dfrac{x}{y}\rfloor，每一次若加入一个以前的数的权值，权值一定 \le y，那么 z 最多增加一。若加入一个新的数的权值，则 z 不会增大。那么暴力维护 z 的变化，复杂度是正确的，而且避免了取模。

提交记录