现在给出一个排列a[],现在按照给定顺序删除这个序列中的元素,求每次删除的元素相邻的两个元素分别为多少
请用数组模拟链表的方式实现
Input
第一行一个数 n,表示排列长度为 n
第二行包括 n 个数,表示排列a[]
第三行包括 n 个数,表示删除的顺序p[],pi 表示第 i 次操作删除原排列中的 pi (pi的意思是排列中第i个位置上的数)
Output
输出包括 n 行,每行包括两个数,表示第 i 次删除时左右两边的数为多少,不存在输出 −1
Constraint
2≤n≤200000
Sample Input
5
1 3 2 5 4
4 2 5 1 3
Sample Output
2 4
1 2
2 -1
-1 2
-1 -1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000100;
int l[N], r[N], e[N];
int idx;
int n;
int op;
int k, x;
int m,s;
void init(){
// 0 是左端点, 1 是右端点
l[1] = 0;
r[0] = 1;
idx = 2;
}
//将 x 插在下标是 k 的点后
void add(int k, int x){
e[idx] = x;
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx;
idx ++;
}
//删除下标是 k 的点
void remove(int k){
e[k]=-1;
r[l[k]] = r[k];
l[r[k]] = l[k];
if(m+1==s){
cout<<e[k-1]<<" "<<e[k+1]<<endl;
return ;
}/*else if(e[r[k]]==0&&e[l[k]]!=0){
cout<<-1<<" "<<e[l[k]]<<endl;return ;
}else if(e[l[k]]==0&&e[r[k]]!=0){
cout<<e[r[k]]<<" "<<-1<<endl;return ;
}else if(e[l[k]]==0&&e[r[k]]==0){
cout<<"-1 -1"<<endl;return ;
}*/
cout<<e[r[k]]<<" "<<e[l[k]]<<endl;
return ;
}
int main()
{
cin >> n;
s=m=n;
n--;
int i=2;
init();
cin>>k;
add(l[1], k);
while(n --){
int p=k;
cin >> k;
add(l[p + 1], k);
}
e[s+1]=-1;
e[1]=-1;
while(m--){
cin>>k;
remove(k+1);
}
}