P12307 题解

· · 题解

怎么没题解，来交一个题解。

我个人觉得这个题和 HDU 某一场的 1004 如出一辙，在那个题的题解中也提到了，将子区间的描述改为子序列是不影响答案的。非常巧合的是打这一场时这个题也是我过的。

由于这个原因，以下将不加证明的给出结论。

首先题目意思就是每次选一个简单环对上面的权值 cyclic shift，问能否通过操作把点权序列 p 变为 q。

对边双考虑，显然每个边双是独立的，可以分别做。

特判掉点权的可重集不相等的情况。然后直觉告诉我们这样操作几乎可以将 p 任意排列。

但是有特判，注意到对一个奇环 shift 是不改变逆序对数奇偶性的，所以如果边双内没有偶环且逆序对数奇偶性不相等就直接 NO。

但是考虑还有特判，如果整个边双就是一个环，那么显然只能生成循环同构的序列，这种情况使用最小表示法/哈希等任意你喜欢的算法判掉即可。

但是考虑还有特判，如果 p 存在相同元素的话，我们上面针对逆序对数的约束就没用了，因为可以通过钦定两个相同元素的大小关系任意改变逆序对数奇偶性。

可以证明剩下的情况都是 YES。具体实现的话，对于找偶环这件事情，在 dfs 树上讨论一下即可。复杂度 O(n\log n+m)，瓶颈是求逆序对。