算法提高 盾神与条状项链 双向链表

       思路：用双向链表，next[x] = y表示颜色为x的珠子的下一个珠子的颜色是y，PRe[x] = y表示表示颜色为x的珠子的上一个珠子的颜色是y。时间复杂度是O(n + m)

#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>#include <utility>#include <string>#include <iostream>#include <map>#include <set>#include <vector>#include <queue>#include <stack>using namespace std;#pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10#define inf 0x3f3f3f3f#define PI pair<int, int> typedef long long LL;const int maxn = 1e5 + 5;int next[maxn], pre[maxn];int n, m, head, len;//双向链表 void Insert(int key, int pos1, int pos2) {	++len;	next[key] = pos2;	next[pos1] = key;	pre[key] = pos1;	pre[pos2] = key;}void init(int n) {	head = 0; next[head] = 0; pre[head] = 0;	int x, prev = 0;	for(int i = 0; i < n; ++i) {		scanf("%d", &x);		Insert(x, prev, next[prev]);		prev = x;	}}void Delete(int key, int pos1, int pos2) {	--len;	next[pos1] = pos2;	pre[pos2] = pos1;}void print() {	printf("%d/n", len); 	int nex = next[head];	while(nex) {		printf("%d ", nex);		nex = next[nex];	}	printf("/n");}int main() {	while(scanf("%d%d", &n, &m) == 2) {		len = 0;		init(n);		char op[5];		int x, y;		for(int i = 0; i < m; ++i) {			scanf("%s", op);			if(op[0] == 'A') {				scanf("%d%d", &x, &y);				Insert(y, pre[x], x);			}			else {				scanf("%d", &x);				Delete(x, pre[x], next[x]);			}		}		print();	}	return 0;}如有不当之处欢迎指出！