自动搬运

查看原文

来自洛谷，原作者为

	q1uple ???????

搬运于2025-08-24 22:14:01，当前版本为作者最后更新于2024-07-22 22:04:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

首先，每一次两只鞋子的匹配必须是相邻的。证明是容易的，比如 $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";
}