日志 12.24

DS 题，主题平衡树和可并堆。

T2 未知来源模拟赛题

题意简述：给一棵有根树，树上权值形成排列，对 \(i\in[1,n]\) 依次执行：选择子树内（包括 i 自己）的一个 j，并交换 \(a_i,a_j\)。问是否能在 n 次操作之后使 \(\forall i:a_i=i\)，如有须构造方案。

容易注意到，有解的必要条件是每个置换环所有结点都在一条祖孙链上，因为转弯必须在 lca 或它上面的某处交换两次，手玩易知。

于是只判这个必要条件交上去，发现 PC 完了，这说明结论充分，只须对链上的情况给出构造即可。

唐完了。捏着正确的充要条件但是觉得不是对的，对一组手搓的 Hack 觉得无解，并暴搜写挂认为新结论正确，还拿去招摇撞骗。

考虑按顺序构造，如果当前点 u 是置换环里深度最大的点就不动他，否则找一个 v 跟他换，那么会换出来两个置换环，因为 u 之后不能再动了，所以一定要让 u 是新置换环的最深点。手玩得到，有且仅有一个 v 满足条件：u 沿置换环倒着找，第一个大于其深度的。

于是写棵平衡树维护这个东西，一次交换是把一个区间提出来并合并另外两段，找 v 直接两次树上二分。

提问：已知结点编号怎么把他分裂出来呢？答案是额外维护一个父亲，暴力上跳求 rank，然后按 sz 分裂。

维护父亲时的变化量：分裂合并两次连边带上父亲边；分裂时清空当前结点父亲。

今天调了一个小时的大饭：

树上二分：

若 右儿子满足条件：返回递归右儿子。

否则若 自己满足条件：返回自己。

否则：返回递归右儿子。

T1 P3274

噔 噔 咚

这个题思路真的很简单。考虑把每个僵尸拆点，表示成往上走和往下走，然后就能连边形成若干链。如果一只僵尸似了那么就交换对应两条链的后缀，这可以用平衡树实现。

然后一堆细节。待我做完再总结。

闲话部分

没有闲话。晚上被头痛肘回家了。我植物大战僵尸还没吃完。