专栏文章

Luna loves Richard.

AAmoribus
P9310题解参与者 9已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@mipd28eo
此快照首次捕获于
2025/12/03 10:01
3 个月前
此快照最后确认于
2025/12/03 10:01
3 个月前
查看原文
Luna 爱磕 cp。

题目大意

给定一个长度为 2n2n 的序列 aa，aia_i 为 1∼n1\sim n 的整数。其中，每个整数出现且仅出现两次。
你可以进行两种操作：交换两个相邻的数的位置，或者删除两个相邻且相同的数。
最后要使序列为空，求最少进行的操作数。

思考

我们不妨考虑两对情侣。一对是 Richard&Ransing，还有一对是 Luna&Lucas。我们设他们的位置分别为 R1,R2,L1,L2R_1,R_2,L_1,L_2。
它们的位置应该有以下三种情况。
  • 完全不相交。不妨设 R1<R2<L1<L2R_1<R_2<L_1<L_2。我们没必要考虑他们互相之间的影响。先让谁相遇都是一样的。
  • 包含关系。不妨设 R1<L1<L2<R2R_1<L_1<L_2<R_2。这个时候我们要让靠里面的情侣 Luna&Lucas 先离开，因为这样可以使靠外的情侣 Richard&Ransing 跨过更少的人相遇。
  • 部分相交。不妨设 R1<L1<R2<L2R_1<L_1<R_2<L_2。这样也是让谁先相遇都一样。
因为只有包含关系必须保证距离近的情侣先走，其它关系让哪一对情侣先走都无所谓，因此我们让离得近的情侣先走一定是最优的。
将每一对情侣之间的距离排序，然后计算求解即可。

实现

考虑交换怎么弄。你发现一对情侣的相遇过程当中，无论两个人怎么走，他们离开之后剩下的序列一定是固定的，因此爱怎么走怎么走，我们不妨就让左边的人走向右边。这样的话，如果两个人之间隔了 kk 个人，就一定走 kk 步。
这个问题就比较容易了，怎么处理下标 ll 到 rr 之间还存在多少个人呢？你可以想到线段树或者树状数组，然后维护一下就可以了，只需要单点修改和区间求和操作。
可能会有疑问：修改间隔人数后的情侣距离关系还能保证正确吗？
其实不会影响答案的正确性，因为这种修改不会影响到处于包含关系的情侣距离大小的排序，而只有这种情况的交换顺序是我们特别关注的。
别忘了开 longlong。写的线段树，其实我觉得线段树比树状数组简单。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+7;
int n,a[N],seg[N<<2],ans,tmp=0;
struct CP{
	int l,r,d;
}cp[N];
bool cmp(CP X,CP Y){
	return X.d<Y.d;
}
void add(int p,int l,int r,int x,int v){
	if(l==r){
		seg[p]+=v;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) add(p<<1,l,mid,x,v);
	if(x>mid) add(p<<1|1,mid+1,r,x,v);
	seg[p]=seg[p<<1]+seg[p<<1|1];
}
int query(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		return seg[p];
	}
	int mid=l+r>>1,pre=0;
	if(x<=mid) pre+=query(p<<1,l,mid,x,y);
	if(y>mid) pre+=query(p<<1|1,mid+1,r,x,y);
	return pre;
}
signed main()
{
	cin>>n;
	for(int i=1;i<=2*n;i++){
		cin>>a[i];
		if(!cp[a[i]].l) cp[a[i]].l=i;
		else cp[a[i]].r=i;
	}
	for(int i=1;i<=n;i++) cp[i].d=cp[i].r-cp[i].l;
	for(int i=1;i<=2*n;i++){
		add(1,1,2*n,i,1);
	}
	sort(cp+1,cp+n+1,cmp);
	for(int i=1;i<=n;i++){
		int LP=cp[i].l,RP=cp[i].r;
		int dist=query(1,1,2*n,LP,RP)-2;
		ans+=dist+1;
		add(1,1,2*n,LP,-1);
		add(1,1,2*n,RP,-1);
	}
	cout<<ans<<endl;
	return 0;
}

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...