小红拿到了一个数组,初始数组为空,她希望你实现以下两种操作:

  1. 输入 1 x y,将x插入在元素y的右边。保证此时数组中没有元素等于x,且数组中存在一个y。特殊的,如果将x插入在数组的最左边,则 y=0
  2. 输入 2 x,将元素x删除。

请你在所有操作后输出整个数组。

输入格式

第一行输入一个正整数 q,代表操作次数。

接下来的 q 行,每行输入两个整数 2 x 或者三个整数 1 x y,代表一次操作。操作含义如题目说明。

数据范围:

1<=q<=2*10^5

1<=x<=10^9

0<=y<=10^9

输出格式

第一行输出一个整数 n,代表最终数组的大小。

第二行输出 n 个正整数,代表最终的数组。

输入样例:

4
1 2 0
1 7 2
1 1000 7
2 7

输出样例:

2
2 1000

说明:

第 1 次操作后,数组为[2]。

第 2 次操作后,数组为[2,7]。

第 3 次操作后,数组为[2,7,1000]。

第 4 次操作后,数组为[2,1000]。

题目分析

插入删除操作频繁,我们考虑使用链表来完成。 恰巧 list 的底层正是链表,我们还可以用哈希表存下对应元素的迭代器来加速查找。

代码实现

#pragma GCC optimize O(2)
#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;

int q, op, x, y;
list <int> ls = {0};
unordered_map <int, list <int>::iterator> mp = {{0, ls.begin()}};
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> q;
    while(q--) {
        cin >> op;
        if(op == 1) {
            cin >> x >> y;
            auto pos = mp[y];
            ls.insert(++pos, x);
            mp[x] = --pos;
        }
        else {
            cin >> x;
            ls.erase(mp[x]);
            mp.erase(x);
        }
    }
    cout << mp.size() - 1 << '\n';
    for(auto it = ++ls.begin(); it != ls.end(); ++it) cout << *it << ' ';
    return 0;
}
分类: ListNode

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status