你说的对，但这就是IOI题目吗？

· · 题解

怎么第一篇题解折磨抽象，切了来写一篇题解。

首先，每一次两只鞋子的匹配必须是相邻的。证明是容易的，比如 x1，y1，x2，y2 这一个序列，如果匹配 x1，y2 和 x2，y1，区间是有交集的。而匹配相邻的就是无交集的。

但是接下来还有一个问题，x1，y1 是谁找谁。

接着我们发现这个东西很像冒泡排序，回顾一下冒泡排序的过程，交换的过程都是单向的从一边到另外一边，如果不这样，那么我们就需要花费更多的代价。

所以我们所有的操作都是单向的，且与最近能匹配的匹配。

注意到数据范围，我们要优化。

我们可以提前记录所有鞋子的位置（开 n 个 vector），接着从右往左对于每个鞋子，找到未匹配的一个鞋子（我们把匹配过的鞋子删了），注意到直接计算中间剩余的鞋子很慢，我们可以使用数据结构进行优化（比如树状数组），最初把所有数赋值为 1，如果匹配就为 0。区间求和即可。

这样我们就做完了，下面是代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5,mod=1e9+7,INF=2e9;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
#define qmi(a,b) a=min(a,b)
#define qma(a,b) a=max(a,b)
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define atrep(i,l,r) for(int i=(r);i>=(l);i--)
#define vec vector<int>
#define pb push_back
char eof_flag;
template<typename T>char read(T*s){if(eof_flag)return 0;T k=0,f=1;
    char c=getchar();while(c!='-'&&(c<'0'||c>'9')){if(c==EOF){eof_flag=1;return 0;}
        c=getchar();}f=(c=='-')?-1:1;k=(c=='-')?0:(c^48);c=getchar();while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();
    if(c==EOF)eof_flag=1;(*s)=f>0?k:-k;return 1;}
template<typename T>void pnt(T x){static char stk[22],*top;for(top=stk,x<0?(putchar('-'),x=-x):0;x;*top++=x%10+'0',x/=10);for(top==stk?putchar('0'):0;top>stk;putchar(*--top));putchar('\n');}
int c[N],vis[N],res=0,indax[N];
vec ve[N];
int n;
struct BIT{
    int a[N];
    void add(int x,int d){while(x<=2*n){a[x]+=d;x+=(x&-x);}return;}
    int ask(int x){int res=0;while(x){res+=a[x];x-=(x&-x);}return res;} 
}T;
signed main(){
    cin>>n;
    rep(i,1,2*n){
        cin>>c[i];
        ve[c[i]+n].push_back(i);// 因为有负数,下标偏移
        T.add(i,1);
    }
    atrep(i,1,2*n){
        if(vis[i])  continue;
        ve[c[i]+n].pop_back();
        int now=ve[-c[i]+n].back();
        ve[-c[i]+n].pop_back();
        vis[now]=1;
        T.add(now,-1);
        res+=T.ask(i-1)-T.ask(now-1);
        if(c[i]<0)  res++;
    }
    cout<<res<<"\n";
}