ABC421F题解

Henry2012 · 2025-09-10 11:06:32 · 题解

题意：有一个数组，初始为 [0]。有两种操作，一是把当前操作编号 i 插入到 x 后面，另一种是求两个数 x 和 y 之间的数之和，并把它们删掉（不包括两端）。

正解

因为是有插入与删除，考虑使用链表（单向即可）。查询时，因为 x 的位置可能在 y 后面，所以从 x 和 y 开始一起往后跳，有一个跳到另一个时结束。代码不放了。（其实是我没写）

歪解

赛场上发现 x 的位置可能在 y 后面之后就放弃链表了。然而我不会平衡树。

发现可以使用分块 + 定期重构，不会的左转数列分块入门 6。维护每个数属于的块的编号 loc，每个块的大小 sz 与和 sum，如果有块的大小大于 2\sqrt{n}（n 是当前存在的数的数量）就全部重构。复杂度 O(Q\sqrt{Q})，显然跑不满且 AT 神机。最慢的点 1187ms，完全不卡常。

AC 记录

这个题比较特殊，经常会把一个块删光，所以调一下块长可能会更快，不过我没试。