Description

维护一个双链表，双链表初始为空，支持以下五种操作：

    1. 在最左侧插入一个整数。

    2. 在最右侧插入一个整数。

    3. 将第 $k$ 个插入的整数删除。

    4. 在第 $k$ 个插入的整数左侧插入一个整数。

    5. 在第 $k$ 个插入的整数右侧插入一个整数。

共进行 $m$ 次操作，最后从头到尾输出链表。

注意：第 $k$ 个插入的整数不是链表的第 $k$ 个整数，而是整个过程中第 $k$ 个插入链表的整数。

Input Format

第一行一个整数 $m$ 表示操作次数。

接下来 $m$ 行，每行包含一个操作命令，操作命令可能是以下五种：

    $1.$ L x，表示在链表的最左端插入整数 $x$。

    $2.$ R x，表示在链表的最右端插入整数 $x$。

    $3.$ D k，表示将第 $k$ 个插入的整数删除。

    $4.$ IL k x，表示在第 $k$ 个插入的整数左侧插入一个整数。

    $5.$ IR k x，表示在第 $k$ 个插入的整数右侧插入一个整数。

Output Format

一行若干个整数表示操作结束后，链表从头到尾的整数。

10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2

8 7 7 3 2 9

Hint

$1≤m≤10^5,1≤x≤10^9$

const int N=1e5+3;
int a[N],l[N],r[N],idx=2;
void init(){
r[0]=1;
l[1]=0;
}
void rinsert(int k,int x){}
void del(int k){} 

Source

模板