Luna 爱磕 cp。

题目大意

给定一个长度为 $2n$ 的序列 $a$，$a_i$ 为 $1\sim n$ 的整数。其中，每个整数出现且仅出现两次。

你可以进行两种操作：交换两个相邻的数的位置，或者删除两个相邻且相同的数。

最后要使序列为空，求最少进行的操作数。

思考

我们不妨考虑两对情侣。一对是 Richard&Ransing，还有一对是 Luna&Lucas。我们设他们的位置分别为 $R_1,R_2,L_1,L_2$。

它们的位置应该有以下三种情况。

• 完全不相交。不妨设 $R_1<R_2<L_1<L_2$。我们没必要考虑他们互相之间的影响。先让谁相遇都是一样的。
• 包含关系。不妨设 $R_1<L_1<L_2<R_2$。这个时候我们要让靠里面的情侣 Luna&Lucas 先离开，因为这样可以使靠外的情侣 Richard&Ransing 跨过更少的人相遇。
• 部分相交。不妨设 $R_1<L_1<R_2<L_2$。这样也是让谁先相遇都一样。

因为只有包含关系必须保证距离近的情侣先走，其它关系让哪一对情侣先走都无所谓，因此我们让离得近的情侣先走一定是最优的。

将每一对情侣之间的距离排序，然后计算求解即可。

实现

考虑交换怎么弄。你发现一对情侣的相遇过程当中，无论两个人怎么走，他们离开之后剩下的序列一定是固定的，因此爱怎么走怎么走，我们不妨就让左边的人走向右边。这样的话，如果两个人之间隔了 $k$ 个人，就一定走 $k$ 步。

这个问题就比较容易了，怎么处理下标 $l$ 到 $r$ 之间还存在多少个人呢？你可以想到线段树或者树状数组，然后维护一下就可以了，只需要单点修改和区间求和操作。

可能会有疑问：修改间隔人数后的情侣距离关系还能保证正确吗？

其实不会影响答案的正确性，因为这种修改不会影响到处于包含关系的情侣距离大小的排序，而只有这种情况的交换顺序是我们特别关注的。

别忘了开 longlong。写的线段树，其实我觉得线段树比树状数组简单。

#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;
}