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 真的简单。

热门相关:爱夜蒲之备胎上位   3天的休假   疯狂少女营国语   性爱不眠夜   我朋友的老姐2