题目描述

blablabla

样例

blablabla

算法1

(双链表) $O(n)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int e[N],l[N],r[N];
int idx;

void init()
{
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

void l_insert(int x)
{
    e[idx] = x;
    r[idx] = r[0];
    l[idx] = 0;
    l[r[0]] = idx;
    r[0] = idx;
    idx++;
}

void r_insert(int x)
{
    e[idx] = x;
    l[idx] = l[1];
    r[idx] = 1;
    r[l[1]] = idx;
    l[1] = idx;
    idx++;
}

void k_delete(int k)
{
    //if (k < 1 || k+1 >= idx) return; 
    l[r[k+1]] = l[k+1];
    r[l[k+1]] = r[k+1];
}

void Il_insert(int k,int x)
{
    //if (k < 1 || k+1 >= idx) return;
    e[idx] = x;
    l[idx] = l[k+1];
    r[idx] = k+1;
    r[l[k+1]] = idx;
    l[k+1] = idx;
    idx++;
}

void IR_insert(int k,int x)
{
    //if (k < 1 || k+1 >= idx) return;
    e[idx] =  x;

    r[idx] = r[k+1];
    l[idx] = k+1;
    l[r[k+1]] = idx;
    r[k+1] = idx;
    idx++;

}

int main()
{
    int n;
    cin >> n;
    init();

    while(n--)
    {
        string c;
        cin >> c;

        if(c == "L")
        {
            int x;
            cin >> x;
            l_insert(x);
        }

        else if(c == "R")
        {
            int x;
            cin >> x;
            r_insert(x);
        }

        else if(c == "D")
        {
            int k;
            cin >> k;
            k_delete(k);
        }

        else if(c == "IL")
        {
            int x,k;
            cin >> k >> x;
            Il_insert(k,x);
        }

        else 
        {
            int x,k;
            cin >> k >> x;
            IR_insert(k,x);
        }
    }
    int i = r[0];
    while(i != 1)
    {
        cout << e[i] << " ";
        i = r[i];
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla