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

_Missile_ · 2025-09-12 09:37:27 · 题解

题意

有一个数组 a，初始时只有一个元素 0，你需要完成 q 次操作。设当前正在执行第 i 次操作。

• 1 x：将数列中所有值为 x 的元素后面添加一个数 i。
• 2 x y：设数组中元素 x 出现的下标为 id_x，元素 y 出现的下标为 id_y，你需要输出 \sum\limits_{j = \min(id_x, id_y)} ^ {\max(id_x, id_y)} a_j。然后将 \min(id_x, id_y) + 1 \sim \max(id_x, id_y) - 1 下标之间的所有元素删除。

题目保证，任何时候数组中都不会出现重复的元素。

思路

一眼的链表。

我们建双向链表，a_i.pre 表示我们模拟的虚拟数组中 值为 i 的前一个元素的 值，a_i.suf 表示后一个元素的 值。

我们对两种操作分类讨论：

• 1 x：我们可以直接在链表上插入，学过链表的应该都会。时间复杂度 O(1)。
• 2 x y：因为我们不知道到底是元素 x 的位置在前还是 y 的位置在前，因此我们可以用两个变量 X, Y，分别从 x, y 同时 开始往后遍历，如果 X 先遍历到 y，就输出 X 经过的数之和，如果 Y 先遍历到 x，就输出 Y 经过的数之和。输出最终结果，然后删除元素 x 到元素 y 之间的数。我们在判断“X 先到 y 还是 Y 先到 x”时就可以求出来谁在前面谁在后面了，方便删除。总时间复杂度 O(q)。

AC 记录

注意事项

我们在进行所有查询之前，要先将链表所有节点进行初始化，即对于所有的 1 \le i \le q + 1，将链表数组 a 的 a_i.suf 变为 q + 1。为什么呢？想一想，如果我们不初始化的话，那么我们执行 2 操作时，操作过程可能会成这样：

明显，正确的段应该是 1 \to 3 \to 2，但是我们没有初始化，导致 X 跑到了 0，然后跑到了 y 的位置，答案就会算错。因此，我们需要初始化 .suf = q + 1。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 5e5 + 5;

int q;

struct List{
    int pre, suf;
} a[N];

void Add(int x, int i){
    a[i].pre = x;
    a[i].suf = a[x].suf;
    a[x].suf = i;
}

void Del(int x, int y){
    a[y].pre = x;
    a[x].suf = y;
}

void solve(int i){
    int f, x, y;
    cin >> f >> x;
    if(f == 1){
        Add(x, i);
    }else{
        cin >> y;
        if(a[x].suf == y || a[y].suf == x){
            cout << "0\n";
            return;
        }
        int X = x, Y = y;
        ll ans1 = 0, ans2 = 0;
        while(1){
            if(a[X].suf == y){
                ans1 += X;
                ans2 = -1;
                break;
            }
            if(a[Y].suf == x){
                ans2 += Y;
                ans1 = -1;
                break;
            }
            if(X != x){
                ans1 += X;
            }
            if(Y != y){
                ans2 += Y;
            }
            X = a[X].suf;
            Y = a[Y].suf;
        }
        cout << max(ans1, ans2) << '\n';
        if(a[X].suf == y){
            Del(x, y);
        }else{
            Del(y, x);
        }
    }
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> q;
    for(int i = 0; i <= q + 1; i++){
        a[i].suf = q + 1;
    }
    for(int i = 1; i <= q; i++){
        solve(i);
    }
    return 0;
}