题解：AT_abc421_f [ABC421F] Erase between X and Y

· · 题解

AT_abc421_f [ABC421F] 删除 X 到 Y 题解

题目链接

题目大意

有一个长度为 1 的序列 A，包含一个元素 0。

有 Q 次操作，第 i 次操作输入 op 代表操作类型。操作类型一给出 x，在 A 序列值为 x 的元素的后面插入值为 i 的元素；操作类型二给出 x 和 y，将 A 中值为 x 和 y 的元素之间的所有元素删除，并输出删除的元素的总和。

思路及实现

这道题看起来需要很多的序列查找元素值，所以卡住时间。

但是可以通过链表破局。针对操作一，只要找到元素 x 就可以 O(1) 插入。所以考虑如何快速找到元素。

这里由于初始元素值为 0，而后续插入的元素值只可能在 [1, Q] 范围内，所以各个元素值互不相同。这说明了如果我们能够记录每个元素在链表中的位置，就可以 O(1) 找到值相对应的元素。

由于最多插入 Q 个元素，开一个长度为 Q + 1 的数组申请出链表的全部空间，并且钦定数组下标为 i 处是值为 i 的链表节点，其 next 指针则是数组此处的值。这样一来，就实现了 O(1) 的查找和插入。

操作二如何在此基础上实现？如果找到了 x 和 y 的位置，只需要让 x 的 next 指向 y 即可删除。但是如何求和？朴素的想法是从 x 开始沿着 next 指针找到 y，并且统计和。但是这种方法的时间复杂度是否可行？

考虑均摊，总共只会有 Q 个元素被加入，所以最多删除 Q + 1 个元素，并且实际上不可能达到这个值，那么遍历的元素一定会被删掉，删掉的元素不会再插入，所以最多遍历 Q 数量级个元素，总体复杂度 O(Q)。

这种方法可行，但是还有最后一个问题。我们不知道 x 和 y 谁在单向链表中更靠前，可能其中之一通过 next 不能走到对方。此时可以考虑同时从 x 和 y 出发，途中记录总和，并在到达链表尾或对面时停止，将唯一那个到达对面的记录的总和输出即可。

AC Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll Q, op, x, y;
ll nxt[500005];
int main()
{
    scanf("%lld", &Q);
    nxt[0] = -1;
    for (int i = 1; i <= Q; i++)
    {
        scanf("%lld%lld", &op, &x);
        if (op == 1)
        {
            nxt[i] = nxt[x];
            nxt[x] = i;
        }
        else
        {
            scanf("%lld", &y);
            ll cx = x, cy = y, sx = 0, sy = 0;
            while (1)
            {
                if (nxt[cx] != -1)
                {
                    cx = nxt[cx];
                    if (cx == y)
                    {
                        printf("%lld\n", sx);
                        nxt[x] = y;
                        break;
                    }
                    else
                        sx += cx;
                }
                if (nxt[cy] != -1)
                {
                    cy = nxt[cy];
                    if (cy == x)
                    {
                        printf("%lld\n", sy);
                        nxt[y] = x;
                        break;
                    }
                    else
                        sy += cy;
                }
            }
        }
    }
    return 0; 
}