y总代码是真牛，remove（k+1）这样头结点和尾结点就永远不会被删掉了。

确实

### 简化小技巧。把head初始化为 0，tail初始化为 N - 1，idx初始化为 1，第 k 个插入的数的下标就是 k。

#include<iostream>
#include<string>

using namespace std;

const int N = 1e5 + 10;
int ls[N], l[N], r[N], head, tail, idx;

void init(){
    head = 0;
    tail = N - 1;
    r[head] = tail;
    l[tail] = head;
    idx = 1;
}

void remove(int k){
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

void rightInsert(int k, int x){
    ls[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

int main(){
    int m;
    char op[5];
    int k, num;

    init();
    cin>>m;
    while(m--){
        scanf("%s", op);
        if(string(op) == "R"){
            cin>>num;
            rightInsert(l[tail], num);
        }else if(string(op) == "D"){
            cin>>k;
            remove(k);
        }else if(string(op) == "L"){
            cin>>num;
            rightInsert(head, num);
        }else if(string(op) == "IL"){
            cin>>k>>num;
            rightInsert(l[k], num);
        }else if(string(op) == "IR"){
            cin>>k>>num;
            rightInsert(k, num);
        }
    }

    int p = r[head];
    while(p != tail){
        cout<<ls[p]<<" ";
        p = r[p];
    }

    return 0;
}

卧槽牛逼(破音——————)

那此时的head = 0， head是指向下一个的指针吗
我看着单链表head = -1； 表示head指向的下一个为空

妙不可言

请问这时的head为什么不能够等于-1呢

y总的模板挺有意思的，单链表里面 head直接就是第一个节点的下标，双链表里面就多了两个哑节点…感觉单链表里面也可以加入头部哑节点，避开在头部插入时的单调操作。

好理解

感觉“单链表里面 head直接就是第一个节点的下标”这个表述有点不准确。
因为单链表模板中head=-1，-1只是一个数，并不代表某一下标，毕竟若-1作为下标访问数组是属于越界的。
而单链表中head会用-1标记，我想是因为并不存在head=-1时会被e[]或ne[]数组访问的情况，所以才能放心让head初始化为-1，并且让-1作为链表结尾
（我想这也就是双链表模板中采用0 1作为哑节点，宁愿让第k个数插入的使用中都得k+1，也不使用-1 0作为哑节点的原因）

0 1 2 3 4
1 2 3 4 5,    要k - 1才能对齐下标
0 1 2 3 4
      1 2 3     要k + 1才能对齐下标

为啥remove（k+1）里面是k+1嘞大佬们

元素是从下标为2的位置开始加入，所以你第k个插入的元素，比如是第3个插入的元素，它的下标对应4,即:K+1

理解了大佬

thank u bro,gangster bro,homie bro,u know what i am saying?

m3

我要diss你

迪士尼

我勒个美式男孩

ios::sync_with_stdio(false);
这个是什么意思啊？

cin，cout先把要输出的东西存入缓冲区，再输出，导致效率降低，而这段语句可以来打消iostream的输入输出缓存，可以节省许多时间，使效率与scanf与printf相差无几

谢谢大佬，涨知识了。

但是还是有少部分情况 scanf 和 printf 更快一些

加快cin、cout的速度

超级详细！

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int e[N],l[N],r[N],idx;// 分别用来存 自己的值 左边相连元素的地址 右边相连的地址 自己的地址
void init()//假设最左边的点地址为 0, 最右边的地址为 N-1 
{
    r[0]=N-1;       //这两个点是假想出来的，是为了方便边界处理，要不然又要写一个函数专门处理头和尾
                //因为头和尾只有一边链子 
    l[N-1]=0;
     idx=1;// 0地址已经被用过，从1开始 

}
void add(int k,int x)//在下标为k个元素后插入一个点 
{
//这里自己画个图就能理解了，讲再多都没用
//不过我先解释下他们的含义
// l[idx]--当前点的左边的链子 r[idx]同理

// l[r[k]] 两个大括号嵌套，根据优先级先算里面的，也就是r[k]--第k个点的右边链子连接的点，
//再加上外面的大括号    l[第k个点的右边链子连接的点] 的意思就是 第k个点的右边链子连接的点的左边的链子
//l[r[k]]=idx---意思就是 第k个点的右边链子连接的点的左边的 链子链接到当前点
// idx--理解为当前点的地址
    e[idx]=x;
     l[idx]=k;
    r[idx]=r[k];
    l[r[k]]=idx;
    r[k]=idx;
    idx++;

}
void remove(int k)//删除的第K个点 
{
    l[r[k]]=l[k];
    r[l[k]]=r[k];//r[l[k]]---结合l[r[k]]的含义去理解，画个图就ok了


}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int M;
     cin>>M;
     init();
     while(M--)
     {
        int k,x;
        string op;
        cin>>op;
        if(op=="L")//最左端插入x 
        {
            cin>>x;
            add(0,x);

         }
         else   if(op=="R")
        {

        cin>>x;
            add(l[N-1],x);

         }
          else  if(op=="D")
        {
            cin>>k;
            remove(k);


         }
          else  if(op=="IL")
        {
            cin>>k>>x;
     add(l[k],x);

         }
         else if(op=="IR")
         {
            cin>>k>>x;
            add(k,x);

         }


     }
     for(int i=r[0];i!=N-1;i=r[i])//从首元结点开始遍历 r[0]--头结点右边链子连接的点
     cout<<e[i]<<" ";

return 0;   
 } 

这里可以假设最右边地址是1吗，可以的话怎么改啊

你这画图画的。。。就是欠赞！

#提供一种插入右节点时的不同解决方案。思路类似于删除k节点

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

// l数组存储左节点, r数组存储右节点, e数组存储值
int l[N], r[N], e[N], idx;

void init()
{
    // r[0]为head/头节点/左端点, l[1]为tail/尾节点/右端点
    r[0] = 1; l[1] = 0; idx = 2;
}

// 在k号节点后方插入节点x
void insert(int k, int x)
{
    e[idx] = x; r[idx] = r[k]; l[idx] = k;
    // 方法一：必须先l后r, 不然r[k]发生变化后就无法使用l[r[k]]了
    // l[r[k]] = idx; r[k] = idx;
    // 方法二：无关l,r的赋值顺序, 依据idx的左右端点建立链接
    // 思路与删除k节点很像
    l[r[idx]] = idx;
    r[l[idx]] = idx;
    idx ++;
}

// 删除k节点, 不是k后面的节点!(与单链表有区别)
void del(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main()
{
    int m, k, x; cin >> m;
    char opt;

    init();
    while (m --)
    {
        cin >> opt;
        if (opt == 'L')
        {
            cin >> x; insert(0, x);
        }
        else if (opt == 'R')
        {
            cin >> x; insert(l[1], x); // 无法直接在tial前插入值, 方法的功能为在k右边插入, 所以这里可以写为tail的左端点后插入
        }
        else if (opt == 'D')
        {
            cin >> k; del(k+1); // idx 从2开始计数, 所以 +1 才是实际的 idx位置
        }
        else
        {
            cin >> opt >> k >> x;
            if (opt == 'L') insert(l[k+1], x);
            else insert(k+1, x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';

    return 0;
}

for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << ‘ ‘;//// idx不是从2开始吗，为啥这里的i又是1开始啦？？

最左边的空节点是链表头，这里的i=r[0]指向的是实际插入链表最左边节点的位置，初始化的时候r[0]=1是直接指向了链表尾。只要在最左边进行了插入r[0]指向的是idx了，所以实际上i不是从1开始的 而是从最左边的idx开始

我靠牛逼啊兄弟，想了半天，看到你这我就明白了，但是如果没在最左边插入是不是就要换个写法了，虽然可能没这种情况hh

我自己写得复杂多了，还得更新左右端点，tql，y总。

简明易懂

#include[HTML_REMOVED]
using namespace std;
const int N = 1e5 + 10;
int m;
int e[N],l[N],r[N];
int idx;
void init(){
r[0]=1,l[1]=0;idx=2;
}
void add(int k, int x){
e[idx]=x;
r[k]=idx;
r[idx]=r[k];
l[r[k]]=idx;
l[idx]=k;
idx++;
}
void remove(int k){
l[r[k]]=l[k];
r[l[k]]=r[k];
}
int main(void){ios::sync_with_stdio(false);
cin>>m;
init();
while(m–){
string op;
cin>>op;
int k,x;
if(op==”L”){
cin>>x;
add(0,x);
}else if(op==”R”){
cin>>x;
add(l[1],x);
}else if(op==”D”){
cin>>k;
remove(k + 1);
}else if(op==”IL”){
cin>>k>>x;
add(l[k + 1],x);
}else{
cin>>k>>x;
add(k + 1,x);
}
}for(int i=r[0];i!=1;i=r[i])
cout<<e[i]<<’ ‘;
return 0;
}问一下大佬们，我这个老是 Output Limit Exceeded怎么解决啊

想问一下大佬们，在最右端插入为啥不是（1，x）而是（l[1],x）

1是尾巴，你还能在尾巴后面插吗？在尾巴左边插入，就相当于插到最右端了

那是两个哑节点，不参与值的计算

可以问下，为什么是k+1吗

ios::sync_with_stdio(false);这句是什么意思

通过将ios::sync_with_stdio(false)设置为false，可以禁用C输入输出流与C标准库的同步，从而提高输入输出的性能。但是，禁用同步后，就不能混合使用C的输入输出流和C标准库的输入输出函数，否则可能会导致错误或未定义的行为

懂了，谢谢啦

y总6bi

查找怎么写

对于头节点左右插入不懂的可以看看我的打卡，那有张图我感觉挺好

你好朋友，请教下，第K个右边插入x 那个函数，应该
是先r[idx] = r[k];然后l[idx] = k;吧？

是的