[CF1718D] Permutation for Burenka 瞎扯

尝试回到 1, 2 月份的文风。

感觉，自己思考的时候最好不要乱走，模拟一下考场上的氛围和紧张感，让自己保持专注。

但是当你已经了解了这个问题的全貌后，随机游走一会，仔细观察问题，梳理思路，感觉收获会比较大。

所以看起来我不擅长自己想题，比较擅长马后炮。

[CF1718D] Permutation for Burenka *3300

转化条件，显然题中描述的就是两个序列的笛卡尔树同构。

现在问题转化为：把 \(s\) 和一个未知的 \(d\) 填进去，让你 判定 是否存在合法方案。

对于判定问题，我目前知道的思路：

• 归纳 / 贪心构造。
• 拟合几个必要条件，尝试证明其充分性。
• 对于存在较明显过程性的题目，尝试刻画其最终局面。
• dp 套 dp 那样的判定。似乎可以说是自动机。

初看这个问题我们无从下手，此时我们有一些基本的手段：

• 列出有效信息。本题中我可以知道笛卡尔树上每个节点填的范围 \([l_i, r_i]\)。
• 问题特殊化，考虑一条链上的情况，我们可以发现两件事情：
• 1. 一个粗略的判定方法：对于连续的一段空白点，其对应的值域上 \(s\) 中是否存在相同数量的对应的点。允许一次判定失败。
  2. \(d\) 的取值范围是一段区间。

对于第 2 个性质，我们可以直接猜测，这个结论在原问题上同样成立。

对于第 1 条，我们发现并不好迁移到树上，但是本身问题不大，于是我们考虑 找等价表述。

然后我们又有一个方法是 交换维度考虑。刚刚从树上的角度，现在我们从 \(s\) 的角度想，问题表述为：每个 \(s\) 都能找到一个对应的 \(s_i\in [l_j,r_j]\)。也就是 匹配。

这显然是个必然条件。它充分吗？是的。证明：考虑调整法。不合法的位置必然相邻，而相邻位置限制必然相同。于是我们不断交换直至合法即可。

抽象模型，考虑这个二分图匹配怎么做，如果给定 \(d\) 我们有经典贪心：区间按 \(r\) 排序后能选就选。

还剩一个问题：\(d\) 的取值范围到底怎么求。

事实上 \(d\) 取值是一段区间有若干种理解方式，比如匹配到最后剩下一个区间的交，以及 \(+1,-1\) 之类的调整结合贪心过程理解。

严谨的证明要通过二分图。完美匹配问题考虑 Hall 定理描述。Hall 定理思考的一个 trick 是 优先选自由度高的一方。比如这个题，两边分别是点和区间，应该思考区间。

对 Hall 定理熟悉的话应该了解这种分析方法：我们枚举一段区间 \([L, R]\)，如果有完美匹配那么 \(|\{i|[l_i, r_i]\subseteq [L, R]\}|\le |\{i|s_i\in [L, R]\}|\)。

定义 \(F(L,R)\) 为这一串式子。由于没有完美匹配，存在 \(l,r\) 使得 \(F(l,r)=1\)，那么 \(d\) 必然在所有这些 \([l,r]\) 的交的范围内。得证。

哦其实还有 \(F(l,r)>1\) 的，这种平凡情况直接判了就好。

所以我们知道的 \(d\) 的求法，按 \(r\) 升序，\(l\) 降序分别求解一次，即得 \([L, R]\)。

唉但是感觉这类贪心题还是强行扫描线 + 线段树维护来的舒服啊。