神秘算法速通省选这块

· · 生活·游记

请在阅读本文后食用（管理员麻烦给那篇也过一下谢谢）。

在学习了伟大的扩治算法之后，有同学反映它只适用于高深学术领域，然而其实它在算法竞赛中也有巨大用途，接下来我将以2026省选为例证明其实用性。

现在假设你是一个刚刚进入省选赛场的平凡OIer，而你将会用扩治算法在比赛中证明自己。

Day1，拿到题目的第一眼，你就发现T1显然符合扩治的使用条件，只需要每次在根节点前面添加恰好等于整棵树大小的链，使得新加入的边被选做重边的概率为100%，还不会增加轻边，于是你实现了一次扩治的过程，递归后秒掉T1，此时仅仅用时不到20min。

自信满满的你直接开T3，你发现每次往序列后方加2n个0再补上差的n次操作对答案没有影响，依旧水过。

然而你似乎被T2卡住了，于是你用充足的3-4h左右的时间写下了暴力，拿到了一定分数，D1轻松200+，甚至不用写T2正解。

Day2，拿道题的第一眼你发现T1很水，直接水掉，依旧不管T2，直接开T3，注意到每次询问只要考虑每个节点为根的答案，而在跟前面加一条链之后减掉链的长度，轻松完成一次扩治，递归即可，复杂度只有O(n+m)，然后再打个T2的暴力，依旧200+。

走出考场，在同学们一脸崇拜中，你拿到了400-600tps的分数，轻松进队，这就是扩治的实力！

总结一下，扩治法的本质就是找到问题的扩大版使答案不变或变化量可快速计算，只要题目满足这个性质，你就能快速解决！