2024/10 做题笔记
呜呜呜好多题都没来得及写。你说得对但是我 CSP-S 炸了 [Internal] 1 给你一堆边,区间和区间对应点相连(x \to y, (x+1)\to (y+1), \dots, (x+k)\to (y+k)),求这张图的最小生成树。 区间数量 5e5,节点数 1e5。 暴力来做的话,就是直接建一个并查集然后 merge。写一个启发式合并可以把暴力时间优化很多,但是还是过不了。如果你做过「SCOI2016」萌萌哒,那么事实上这道题可以用类似的一个像是 ST 表上并查集的东西,好像叫做倍增并查 […]