AcWing 827. 双链表

#include <bits/stdc++.h>using namespace std;const int N=1e6+10;int e[N],l[N],r[N],idx;void init(){ //0表示左端点，1表示右端点 r[0]=1; l[1]=0; idx=2;}//在下标是k的点右边，插入xvoid add(int k,int x){ e[idx]=x; r[idx]=r[k]; l[idx]=k; l[r[k]]=idx; r[k]=idx; idx++;}//删除第k个点void remove(int k){ r[l[k]]=r[k]; l[r[k]]=l[k];}int main(){ int m; cin>>m; init(); while(m--){ string op; int k,x; cin>>op; if(op=="L"){ scanf("%d",&x); add(0,x); }else if(op=="R"){ scanf("%d",&x); add(l[1],x); }else if(op=="D"){ scanf("%d",&k); remove(k+1); }else if(op=="IL"){ scanf("%d%d",&k,&x); add(l[k+1],x); }else if(op=="IR"){ scanf("%d%d",&k,&x); add(k+1,x); } } for(int i=r[0];i!=1;i=r[i]) printf("%d ",e[i]); return 0;}