题解：P10785 [NOI2024] 集合

未来姚班zyl · 2024-07-23 17:21:23 · 题解

题目大意

题面十分详细。

题目分析

我们要相信官方数据的强度，并开始发扬人类智慧。

首先瞪出来一个结论：区间 [l,r] 合法，当且仅当对于每一个子区间 [l',r'],A 和 B 中出现的数的次数构成的可重集相等。

考场时我莫名其妙地认为这个结论是对的，也莫名奇妙地发现确实是对的，它和正确的结论有冥冥中的相似，欢迎大佬来证明。

然后只需要维护每个左端点 l 能够延伸到的最靠右的右端点 r，使得对于所有 l\le r'\le r，区间 [l,r'] 中数的出现次数构成的可重集相等，查询只需 RMQ 即可。然而这显然是无法双指针的。

但是聪明的我们可以知道，CCF 的数据是很厉害的，厉害到可以送很多分。

我们做一个亚双指针：每次右移左指针 l 时，将右指针 r 往左移 \frac{\sqrt l}{2}。

只要出题人没有想到这个做法，就卡不掉。

结果果然没卡，虽然连 pretest 都没过，但过了正式数据。

完全不用 Hash，复杂度 O(n\sqrt n)。