B4324 双向链表

点击查看代码

#include<bits/stdc++.h>using namespace std;const int N=500005;
int l[N],r[N];
int n,m;
bool del[N];void insert(int x,int y)
{r[x]=r[y],l[x]=y;l[r[y]]=x,r[y]=x;
}void remove(int x)
{r[l[x]]=r[x],l[r[x]]=l[x];    
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;r[0]=1;for(int i=1;i<=n;i++){r[i]=i+1;l[i]=i-1;}r[n]=0;int op,x,y;while(m--){cin>>op;if(op==1){cin>>x>>y;if(x==y||del[x]||del[y]) continue;remove(x);insert(x,l[y]);}else if(op==2){cin>>x>>y;if(x==y||del[x]||del[y]) continue;remove(x);insert(x,y);}else if(op==3){cin>>x;if(del[x]) continue;remove(x);del[x]=true;}}int p=r[0];if(p==0) cout<<"Empty!";for(p=r[0];p!=0;p=r[p]) cout<<p<<' ';return 0;
}

双向链表的实现，核心就依赖于删除和插入的函数，操作指针时有个小技巧就是要先处理【】带指针的情况，因为覆盖 还有本题也是直接用下标代表数值，可以初始化为r【0】=1//头指针，r[n]=0，相当于末尾无元素