ABC421F题解

题意：有一个数组，初始为 $[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，完全不卡常。

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