Luna loves Richard.

· · 题解

Luna 爱磕 cp。

题目大意

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

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

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

思考

我们不妨考虑两对情侣。一对是 Richard\&Ransing，还有一对是 Luna\&Lucas。我们设他们的位置分别为 R_1,R_2,L_1,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;
}