B.牛牛排队伍——模拟双链表

B.牛牛排队伍——模拟双链表

分析

题目其实很简单，就是双链表的增删查，但是刚开始，直接vis标记删除元素，查找一个位置的前一个用的while不断向前找，但是TLE；毕竟O(n*k)的复杂度，一开始没有考虑时间复杂度，说明只能O(n)线性来解决，刚开始模拟单链表，没用next后继，只用了前驱，有点bug，WA了好几下，后来浩提供的用双链表才过了；注意更新双链表，先更新后继，在更新前驱；

#include <bits/stdc++.h>using namespace std;
typedef long long LL;int n, k;
int pre[1000010];
int ne[1000010];int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> k;for (int i = 1; i <= n; ++i) {pre[i] = i - 1;ne[i] = i + 1;}while (k--) {int op, x;cin >> op >> x;if (op == 1) {//删除x//更新x的前一个元素的后继ne[pre[x]] = ne[x];//更新x的后一个元素的前驱pre[ne[x]] = pre[x];} else {cout << pre[x] << endl;}}return 0;
}