小红数组操作
题目链接:https://ac.nowcoder.com/acm/contest/74362/D
题目描述
小红拿到了一个数组，初始数组为空，她希望你实现以下两种操作：
1.输入 1 \(x\) \(y\) ,将 \(x\) 插入在元素 \(y\) 的右边。保证此时数组中没有元素等于 \(x\) ，且数组中存在一个 \(y\) 。特殊的，如果将 \(x\) 插入在数组的最左边，则 \(y\)=0
2. 输入 2 \(x\) ，将元素 \(x\) 删除。
输入描述:
第一行输入一个正整数 \(q\) ，代表操作次数。
链接：https://ac.nowcoder.com/acm/contest/74362/D
来源：牛客网
接下来的 \(q\) 行，每行输入两个整数 \(2\) \(x\) 或者三个整数 \(1\) \(x\) \(y\)，代表一次操作。操作含义如题目说明。
\(1\)≤q≤\(2\)x\(10^5\)
\(1\)≤\(x\)≤\(10^9\)
\(1\)≤\(y\)≤\(10^9\)
链接：https://ac.nowcoder.com/acm/contest/74362/D
来源：牛客网
输出描述:
第一行输出一个整数\(n\)，代表最终数组的大小。
第二行输出\(n\)个正整数，代表最终的数组。
用两个map分别存一下当前数字左侧是谁和右侧是谁,在map中进行增删,再使用一个队列,将最终的某个map(键指左侧或右侧那个都可以),递归的推进队列,然后输出
注意:此处的两个map仅在增删时同时使用,最终构造数组时只用其中一个map即可;
也可以使用哈希表的方法进行前后向模拟,哈希的方法是直接使用map的方法的1/4时间复杂度
#include<bits/stdc++.h>
using namespace std;
using ll= long long;
constexpr int MOD=998244353;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q,pos{0};
cin>>q;
map<int,int> f,b;
deque<int> dq;
while(q--){
int now;
cin>>now;
if(now==1){
pos++;
int x,y;
cin>>x>>y;
if(b.count(y)>0){
f[b[y]]=x;
f[x]=y;
b.insert({x, b[y]});
b[y]=x;
}
else{
f.insert({x, y});//键指左侧数
b.insert({y, x});//键指右侧数
}
//for(auto [l,r]:f){
// cout<<"f:"<<l<<" "<<r<<"\n";
//}
//for(auto [l,r]:b){
// cout<<"b:"<<l<<" "<<r<<"\n";
//}
//cout<<"-------\n";
}
else{pos--;
int x;
cin>>x;
f[b[x]]=f[x];
b[f[x]]=b[x];
f.erase(x);
b.erase(x);
}
}
auto kpl = *b.begin();
auto now = kpl.second;
while(pos--){
dq.push_back(now);
now=b[now];
}
//for(auto [l,r]:b){
// dq.push_back(r);
//}
cout<<dq.size()<<"\n";
for(auto i:dq){
cout<<i<<" ";
}
}