20251120 总结

今天的题说实话比较【数据删除】，考下来感觉不是很好。

首先是 T1，这是一道水的统计贡献。套路般地拆贡献，然后直接丢进树状数组里算就结束了。唯一令我感到不解的是明明这么普通的一道题，我为什么调了一个多小时。当时我写完了代码，去过小样例，发现过不去，于是想着是不是结论炸了，结果重新推了几万遍结论还是一样，随后发现是我认为绝对不可能错的树状数组写错了。以后一定不能信“绝对”，感觉哪里错了就检查哪里，如果没感觉就直接全都静态查错。

一道克鲁斯卡尔重构树。我考试的时候没往重构树的方向去想，然后一直思考贪心，就成功一分不得。这种看起来信息具有可合并性的大概率可以用 DP，就算是贪心也可以以 DP 的形式体现，所以以后可以把贪心的优先级置于 DP 之后了。

【数据删除】题。讲个好玩的，我之前闲着没事去翻 OI-WiKi，然后发现数学里有个东西叫杨表，试图学习高级数学知识，然后失败，但是记了一下基本知识，今天它考了一道标准杨表，然后就直接套公式就 A 了，正解是打表找规律，然后猜测是这个，就直接 /bangbangt 了。

缝合题目。缝合的第一道是一道原，但是不是我做过的，是 cyc 在长郡那边做的。感觉有点困难，但是这个思路很巧妙：发现两个环上直线相交当且仅当它们在断环为链后相交且不为包含关系，然后直接上并查集加线段树上二分就可以了。第二部分就是简单根号平衡。