开学cf补题（第三周）

#include <bits/stdc++.h>
//#pragma  GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
//#define endl '\n';
using namespace std;
const int N=1e5+7,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=100003;
typedef pair<int,int> PII;

int e[N];//存储每一个需要插入的值
int en[N*2]; //存next值  就是向后的引索
int idx;  //一个下标值用来开新的空间存插入的元素
int head=-1; //一开始的头时-1，这样遍历到尾巴就可以跳出

void  add(int x)  //在头的地方加入新的元素
{
    e[idx]=x;  //存新加入的元素
    en[idx]=head;  //  把新元素的下一个next值指向原来的头
    head=idx;  // 更新现在的头元素
    idx++;  //  加加给下一个新数组开空间
}

void ea(int k) //输出k后面的一个元素
{
    en[k]=en[en[k]];  // 把k元素的指针指向下下一个元素，直接跳过k+1元素，注意下标，因为是从0开始的
}

void in(int k,int x)  // 在第k个元素后面插入x
{
    e[idx]=x;  //存新的元素
    en[idx]=en[k];  //  把新的元素指向k的下一个元素
    en[k]=idx;  //  把k元素指向刚插入的新元素
    idx++;
}
void solve()
{
    int m;
    cin>>m;
    while (m--)
    {
        char c;
        cin>>c;
        if(c=='H')
        {
            int x;
            cin>>x;
            add(x);
        }
        if(c=='D')
        {
            int k;
            cin>>k;
            if (k == 0) head = en[head];
            else
            ea(k-1); //注意删除第k个输入后面的数，那函数里放的是下标，k要减去1，因为你是从0开始的
        }
        if(c=='I')
        {
            int k,x;
            cin>>k>>x;
            in(k-1,x);
        }
    }
    for(int i=head;i!=-1;i=en[i])  // 遍历
    {
        cout<<e[i]<<" ";
    }
}


signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}