小红数组操作题解

本题的重点是找到一个数据结构能降低时间复杂度，传统的数组增删改都需要o(n)，这里我们可以用数组模拟一遍链表，用pre[x]表示当前结点的前一个结点，rear[x]表示当前结点的后一个节点，每次插入删除更新一遍这两个数组即可：

#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
using namespace std;
using ll=long long ;
using pii=pair<int,int> ;
#define endl "\n"

constexpr int N=2e5+10;
constexpr int mod=1e9+7;

void solve()
{
    int n;
    cin>>n;
    
    int h=-1;
    int cnt=0;
    map<int,int>pre,rear;
    for(int i=1;i<=n;i++)
    {
        int op,x,y;
        cin>>op;
        if(op==1)
        {
            cnt++;
            cin>>x>>y;
            
            pre[rear[y]]=x;
            pre[x]=y;
            rear[x]=rear[y];
            rear[y]=x;
            
        }
        else
        {
            cnt--;
            cin>>x;
            
            int x1=pre[x];
            int x2=rear[x];
            pre[x2]=pre[x];
            rear[x1]=rear[x];
        }
        
    }

    int x=0;
    cout<<cnt<<endl;
    
    while(rear[x]!=0)
    {
        cout<<rear[x]<<" ";
        x=rear[x];
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    int t;
    t=1;
    
    while(t--)
    solve();
    return 0;
}