题解：[ABC421F] Erase between X and Y

· · 题解

这里提供两种做法。

官解（链表）

显然可以用链表。为方便起见，可以创 q+1 个点，在第 i 次查询时创建的点代表这个链表中下标为 i 的点。

插入操作不必多说。删除操作时，考虑用一种暴力的思维。从点 x 开始暴力往前跳，直到 y 为止，跳的时候算一下和。最后把 x 号点连向 y 号点即可。

由于每次最多添加一个点，所以点的总数也最多只有 q+1 个，所以这么做均摊 O(q)。

但还有个问题，如果 y 在 x 前面就永远跳不到了。此时有一种简单的想法：两边都跳。但这样会跳一整个链表，直接退化。

但可以考虑同时跳，只要一个跳到了立即结束。这样做依然保证了均摊 O(q)，可以通过。

时间复杂度 O(q)。

Submission

线段树+链表

注意到去除了删除操作后得到了一个序列

- 任何时候，这个序列都是 $A$ 的子序列。 那么可以像线段树一样搞吗？答案是可以的。 先求出元素 $x$ 在 $A$ 中的下标，设其为 $p_i$。 然后将所有数都变成 $0$ 后建一个线段树，再枚举每一个操作编号 $i$。 - 如果是插入操作，就将 $p_i$ 这个位置赋值成 $i$。 - 否则就输出区间 $[\min(p_{u_i},p_{v_i})+1,\max(p_{u_i},p_{v_i})-1]$ 的和，然后将这个区间全赋值成 $0$。记得判空区间。 至于 $A$ 序列怎么求，直接上链表即可。 时间复杂度 $O(q \log^2 q)$，本来打算与卡常死磕到底，结果连时限的 $\frac 1 8$ 都没有跑到。 [Submission](https://atcoder.jp/contests/abc421/submissions/68958967)