brief (usage) introduction for std::list

std::list is a container that supports constant time insertion and removal of elements from anywhere in the container. Fast random access is not supported. It is usually implemented as a doubly-linked list.

—— cppreference

If we use std::list, our code will be a lot shorter and more readable than writing a list by hand.

I’m not going to introduce everything in details including .size() and .clear(). I’ll only tell you how it is stronger than a vector.

• .insert() or .emplace(): When you write .emplace(x,y), where x is an iterator pointing to an element in the same list, it means create an element equal to y before x. i.e. After this operation, it will look like \(\text{[what was in front of x]}\leftrightarrow y\leftrightarrow x\). Note that the iterator x is a must. The time complexity is strictly \(\mathcal O(1)\).
• .erase(): When you erase .erase(x), where x is an iterator pointing to an element in the same list, literally it means to remove it. After this operation, it will look like \(\text{[what was in front of x]}\leftrightarrow \text{[what was behind x]}\). The time complexity is strictly \(\mathcal O(1)\).
• .splice(): It concats two lists. (This one is powerful, but is not used in this problem.)

implementation

You know, we have to know its iterator if we want to process around an element, so we need to store its iterator for each number. Note unlike vector, an iterator never gets spoil unless it’s deleted.

submission

int n,q,a;list<int>qwq;map<int,list<int>::iterator>mmp;
main()
{
	for(read(n);n--;read(a),qwq.emplace_back(a),mmp[a]=--qwq.end());
	read(q);
	for(int o,x,y;q--;)if(read(o),o^2)
	{
		read(x);read(y);
		list<int>::iterator it=mmp[x];++it;
		qwq.emplace(it,y);
		mmp[y]=--it;
	}
	else
	{
		read(x);
		qwq.erase(mmp[x]);
	}
	for(int i:qwq)printf("%d ",i);
}