P9290 Luna likes Love 题解

原题：[洛谷P9310]([P9310 EGOI2021] Luna likes Love / 卢娜爱磕 cp - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

题目大意

给定一个长度为 \(\large 2n(n\leq 10^5)\) 的序列，序列中 \(\large 1\sim n\) 的每一个数都恰好出现两次。

可进行两种操作：

1. 交换两个相邻的数的位置。
2. 若两个相邻的数相同，则删去这两个数。

问最少进行多少次操作可使序列为空。

思路

显然对于序列中一个在前面出现过的数 \(\large a_i\)，我们应该把它交换到与它上一次出现的位置 \(\large lst_{a_i}\) 相邻，并删掉它们，那么代价就是 它们之间剩余的数的数量 \(\large +1\)。

暴力的话，用 \(\large vis_i\) 标记第 \(\large i\) 个数是否已被删去。如果 \(\large a_i\) 在前面出现过，那么让 \(\large ans\) 加上 \(\large\sum\limits_{j=lst_{a_i}}^ivis_j+1\)，然后让 \(\large vis_i=vis_{lst_{a_i}}=1\)。

考虑优化。我们可以开一个前缀和数组 \(\large sum_i\)，表示前 \(\large i\) 个数里被删去的数的个数。带修，所以用树状数组。那么上面的操作可以变为：让 \(\large ans\) 加上 \(\large i-lst_{a_i}-1+1-sum_i+sum_{lst_{a_i}}\)，并 \(\large \operatorname{add}(i,1),\operatorname{add}(lst_{a_i},1)\)。

Code

#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define reg register
#define int long long
using namespace std;
inline int read()
{
	short f=1;
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')	{if(c=='-')	f=-1;c=getchar();}
	while(c>='0'&&c<='9')	{x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
int n,a,ans,c[1000010],lst[500010];
inline void add(int x)	{for(;x<=2*n;x+=x&-x)	c[x]=-~c[x];}
inline int ask(int x)	{int ans=0;	for(;x;x-=x&-x)	ans+=c[x];	return ans;}
signed main()
{
	n=read();
	for(reg int i=1;i<=2*n;i=-~i)
	{
		a=read();
		if(lst[a])
			ans+=i-lst[a]-ask(i)+ask(lst[a]),add(lst[a]),add(i);
		lst[a]=i;
	}
	return printf("%lld",ans),0;
}