[ABC344E] Insert or Erase 题解

FBW2010 · 2024-03-10 13:48:29 · 题解

题意简述

传送门

给定一个数列和 Q 次操作。操作有两种：在 x 后插入 y，或删除 x。

思路

根据题意，我们需要一个能在 O(\log n) 以下插入与删除的数据结构。于是我们可以很容易地想到链表，它的复杂度为 O(n+q)，能通过此题。

由于需要删除指定的一个数，所以要使用双向链表。同时数的范围较大，用数组存不下，而本蒟蒻又不会指针，于是就用 map 代替了数组。

其余详见代码。

代码

#include<bits/stdc++.h>
using namespace std;
int n,q,a[200005];
map<int,int> le,ri; //左指针和右指针 
int main(){
    //初始化 
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        le[a[i]]=a[i-1];
        ri[a[i-1]]=a[i];
    }
    ri[a[n]]=-1;

    //双向链表基操 
    scanf("%d",&q);
    while(q--){
        int f,x,y;
        scanf("%d",&f);
        if(f==1){
            scanf("%d %d",&x,&y);
            //插入 
            ri[y]=ri[x];
            le[y]=x;
            le[ri[x]]=y;
            ri[x]=y;

        }
        else{
            scanf("%d",&x);
            //删除 
            ri[le[x]]=ri[x];
            le[ri[x]]=le[x];

        }
    }

    //遍历输出 
    int x=0;
    while(ri[x]!=-1){
        x=ri[x];
        printf("%d ",x);
    }
    return 0;
}