题目描述

blablabla

样例

blablabla

算法1

blablabla

时间复杂度分析：blablabla

C++ 代码

#include<cstdio>
#include<iostream>

using namespace std;

const int maxn=100005;

struct node{
    int pre,nxt,data;   //前驱和后继
}a[maxn];
int head,tot,rear;//head和rear指向头元素和尾元素

void L(int x)
{
    a[++tot].data=x;
    a[head].pre=tot;
    a[tot].nxt=head;
    head=tot;
    if(!rear) rear=tot;
}

void R(int x)
{
    a[++tot].data=x;
    a[rear].nxt=tot;
    a[tot].pre=rear;
    rear=tot;
    if(!head) head=tot;
}

void D(int k)
{
    if(head==k) head=a[k].nxt;
    if(rear==k) rear=a[k].pre;
    int ll=a[k].pre;
    int rr=a[k].nxt;
    a[ll].nxt=rr;
    a[rr].pre=ll;
}

void IL(int k,int x)
{
    a[++tot].data=x;
    a[tot].pre=a[k].pre;
    a[tot].nxt=k;
    a[a[k].pre].nxt=tot;
    a[k].pre=tot;
    if(head==a[tot].nxt) head=tot;
}

void IR(int k,int x)
{
    a[++tot].data=x;
    a[tot].nxt=a[k].nxt;
    a[tot].pre=k;
    a[a[k].nxt].pre=tot;
    a[k].nxt=tot;
    if(rear==a[tot].pre) rear=tot;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        char s[5];
        scanf("%s",s);
        if(s[0]=='L'){
            int x;
            scanf("%d",&x);
            L(x);
        }else if(s[0]=='R'){
            int x;
            scanf("%d",&x);
            R(x);
        }else if(s[0]=='D'){
            int k;
            scanf("%d",&k);
            D(k);
        }else if(s[1]=='L'){
            int k,x;
            scanf("%d%d",&k,&x);
            IL(k,x);
        }else{
            int k,x;
            scanf("%d%d",&k,&x);
            IR(k,x);
        }
    }
    int t=head;
    while(t)
    {
        printf("%d ",a[t].data);
        t=a[t].nxt;
    }
    cout<<endl;
    return 0;
}