ABC344E Insert or Erase 题解

hellolin · 2024-03-09 22:18:30 · 题解

ABC344E Insert or Erase 题解

前往 [博客暂时关闭] 可能获得更好阅读体验。

不会真的有人写分块重构吧/kx

看到 在某元素后插入 和 删除某元素 这样的操作，第一反应应该是链表。

因为元素都唯一，我们使用一个 unordered_map 存储整数对应链表的哪个指针（或迭代器），插入操作更新被插入元素的指针，之后就是正常的链表模板题啦。

复杂度 O(N)。

代码实现

仅给出核心代码。

手写链表版

不知道为啥赛时 STL 链表写炸了，估计迭代器没处理好，最后是手写的/kel

一定要注意空指针的判定！

有关下面提到的悬空指针，请参阅 维基百科。

namespace hellolin {
int n, q;
struct node {
  int x;
  node *pre, *nxt;
} rt, *cur;
unordered_map<int, node *> it;
void ins(int x, int y) {
  cur = it[x];
  auto tmp = new node();
  tmp->x = y;
  tmp->pre = cur, tmp->nxt = cur->nxt;
  if (cur->nxt) cur->nxt->pre = tmp;
  cur->nxt = tmp;
  it[y] = tmp;
}
void del(int x) {
  cur = it[x];
  if (cur->pre) cur->pre->nxt = cur->nxt;
  if (cur->nxt) cur->nxt->pre = cur->pre;
  // tmp 的作用是防止 cur 变为悬空指针
  // 但我这里 cur 是循环使用的，不加应该也没啥大问题
  auto tmp = cur;
  cur = cur->nxt;
  delete tmp;
  it[x] = nullptr;
}
void main() {
  cin >> n;
  cur = &rt;
  for (int i = 1, x; i <= n; ++i) {
    cin >> x;
    auto tmp = new node();
    tmp->x = x, tmp->pre = cur;
    cur->nxt = tmp, cur = tmp;
    it[x] = cur;
  }
  cin >> q;
  for (int i = 1, op, x, y; i <= q; ++i) {
    cin >> op >> x;
    if (op == 1) {
      cin >> y;
      ins(x, y);
    } else {
      del(x);
    }
  }
  cur = rt.nxt;
  for (; cur; cur = cur->nxt) cout << cur->x << ' ';
  cout << '\n';
}
} // namespace hellolin

std::list 版

果然还是 STL 大法好！

namespace hellolin {
int n, q;
list<int> a;
unordered_map<int, list<int>::iterator> it;
void main() {
  cin >> n;
  for (int i = 1, x; i <= n; ++i) {
    cin >> x;
    it[x] = a.insert(a.end(), x);
  }
  cin >> q;
  for (int i = 1, op, x, y; i <= q; ++i) {
    cin >> op >> x;
    if (op == 1) {
      cin >> y;
      it[y] = a.insert(next(it[x]), y);
    } else {
      a.erase(it[x]);
      it.erase(x);
    }
  }
  for (const int &i : a)
    cout << i << ' ';
  cout << '\n';
}
} // namespace hellolin