首页 > 其他分享 >ABC344E

ABC344E

时间:2024-03-14 20:48:38浏览次数:27  
标签:pre nxt log 复杂度 链表 ABC344E

题意

思路:

  1. 对于1操作可以采用类似链表的方法在元素 \(x\) 的后面直接插入 \(y\) 的值,即 \(nxt_x = y\)。
  2. 对于2操作可以采用链表的删除的方法先令 \(p = nxt_x\) 即 \(x\) 的后继,让 \(pre_p = pre_x\) 然后让 \(nxt_{pre_x} = p\) 但是有一个问题就是输出的时候是从头开始输出的如果头被删除了,那就只能从 \(nxt_{head}\) 作为头开始输出了。

细节:

因为 \(X\) 很大所有不能用数组,可以用 STL 中的 map 实现。总的复杂度为 \(O(T \log_2 N)\) 可以通过。
当然也可以使用离散化来实现,具体的把所有的数来读入,排序后然后二分查找下标最后只会用 \(N\) 的大小的空间,复杂度也是 \(O(T \log_2 N)\)。

标签:pre,nxt,log,复杂度,链表,ABC344E
From: https://www.cnblogs.com/tomxi/p/18073893

相关文章

  • abc344E 维护元素唯一的序列
    给定序列A[N],元素值各不相同,有Q个操作,格式如下:1xy:在元素x后面插入元素y,保证插入时x唯一。2x:将元素x从序列中删除,保证删除时x唯一。输出所有操作完成后的序列。1<=N,Q<=2E5;1<=A[i]<=1E9;A[i]!=A[j]用链表来快速插入和删除,另外还需要map来快速定位,类似LRU的实现。......