珂朵莉的日常 T3题解

# T3.维修圣剑 ## 原题链接：[U19012 维修圣剑](https://www.luogu.org/problemnew/show/U19012) 由于出题人发现本场比赛中第三题尝试的人数最多，同时得分普遍不高（除std外均为20分以下），所以先行放出第三题的题解 同时我再说一遍**这个题不是bzoj原题**，详情请见题解算法三 题解提供三种常见的错误算法（如果你们打些什么奇怪的暴力的话就不要指望题解给出了），以及出题时写出的标准算法（如果大佬有什么更优解欢迎私信告诉我） ### 算法1 无视2号操作，直接维护一个并查集。 可通过子任务3 期望得分10分 ### 算法2 按照题意暴力模拟，每进行一次操作就完整复制一份并查集数组。 可通过子任务1 结合算法1期望得分30分 ### 算法3 这不是可持久化并查集模板题（bzoj 3674）吗？ 写个主席树维护下并查集就好了。 具体做法见bzoj 3674题解 可通过子任务1,2（rope似乎子任务2会被卡常，真不是我故意的QAQ） 结合算法1期望得分60分 ### 算法4 子任务4的数据规模似乎可持久化数据结构根本没法做？ 注意到本题和bzoj 3674的区别：本题的“加密”仅仅对询问进行了处理，而且解密的秘钥只有2种————0或1. 因此我们可以强行读入所有操作后离线处理，对于每个询问，因为可能的解谜后文本只有2种，所以我们对于2种可能的询问都分别计算出答案保存下来。 最后就可以按顺序还原出所有真实的答案。 而并查集本质上是一个数组，可持久化数组有经典的离线做法。 > 不强制在线的可持久化都是耍流氓，我们考虑离线 >发现每个版本都有唯一一个前驱，一定组成一棵树结构 >对这棵树dfs，每到一个点如果是修改就直接修改，询问就直接得到答案 >离开一个点时如果是修改就改回去 --引自[洛谷P3919题解 By @我叫小明0_0](https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P3919) 注意到dfs的时候我们需要撤销操作，因此几乎无法路径压缩（强行压缩的话复杂度也是错的）。我们需要按秩合并的并查集。 按秩合并的并查集单次操作的复杂度为$O(logn)$，因此总复杂度为$O(nlogn)$ 期望得分100分 ## 题解暂时不上传std程序，将在日后视情况上传std.cpp