AT_abc344_e 题解

本文同步发表于洛谷。

赌狗天天输的一集。

赛时各种【数据删除】原因导致没做出来。

大意

给你一个长度为 \(N\) 的序列 \(A=(A_1,\ldots,A_N)\)。保证 \(A\) 中的元素是不同的。

你要处理 \(Q\) 个操作。每个操作是以下两种类型之一：

• 1 x y：在 \(A\) 中元素 \(x\) 后面紧接着插入 \(y\)。当给出此查询时，保证 \(x\) 存在于 \(A\) 中。
• 2 x：从 \(A\) 中删除元素 \(x\)。当给出此查询时，保证 \(x\) 存在于 \(A\) 中。

保证在处理完每一个查询后，\(A\) 都不是空的，并且其元素都是不同的。

处理完所有查询后，打印 \(A\)。

一句人话：模板双向链表。

思路

不知道链表的可以学一下单向链表，B3631。

单向链表大致长这样：

但是！我们的主角双向链表他有出息！他两边都能指！

然后，我高高兴兴的写代码（很简单，按照题面直接做就行），直接就超时了。

我蒙了，为啥？发现是从 head 调到对应位置太耗时间了。

诶，有没有注意到题面说了“保证 \(A\) 中的元素是不同的。” 和“保证在处理完每一个查询后，\(A\) 都不是空的，并且其元素都是不同的。”？

我不要离散化！\(10^9\) 直接 map 启动！

然后代码木大木大了很久还是不对，后来发现是添加的时候忘记更新 x.bef 了…

代码

#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 LL
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
	i128 f=1;
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
void write(i128 x)
{
	if(x>=10)write(x/10);
	putchar(x%10+'0');
}
LL n,a[200010],q,op,x,y,o;
struct nod
{
	LL v,nxt,bef;
}l[400010];
map<LL,LL>f;
int main()
{
	cin>>n;
	l[0].nxt=1;
	rep(i,1,n,1)
	{
		cin>>a[i];
		l[i].v=a[i];
		l[i].nxt=i+1;
		l[i].bef=i-1;
		f[a[i]]=i;
	}
	o=n+1;
	cin>>q;
	while(q--)
	{
		cin>>op;
		if(op==1)
		{
			cin>>x>>y;
			LL t=f[x];
			l[++o]=(nod){y,l[t].nxt,t};
			l[l[t].nxt].bef=o;
			l[t].nxt=o;
			f[y]=o;
		}
		else
		{
			cin>>x;
			LL t=f[x];
			l[l[t].nxt].bef=l[t].bef;
			l[l[t].bef].nxt=l[t].nxt;
			f[x]=0;
		}
	}
	nod u=l[l[0].nxt];
	while(u.v!=0)
	{
		cout<<u.v<<' ';
		u=l[u.nxt];
	}
	return 0;
}

闲话

赛后突然想起一个东西：

我【数据删除】！有个玩意叫 list…

我是消愁。

代码就不放了，STL 真的简单。