AT_arc114_d

非常巧妙的题！

先尝试分析一些简单的性质。

首先，每个棋子可以视作只往一个方向移动若干距离，因为这个操作相当于原本边权为 $0$，每走一步将边权 $\oplus1$。显然走回头路会抵消掉之前走的。也就是说，可以将问题转化成，对于每个 $a_i$ 选择一个 $b_i$，将 $[a_i,b_i]$ 间的边权 $\oplus 1$，使得最后的边权序列满足要求。

其次，棋子移动的终点一定是原本的某个 $a_i$ 或者 $x_i$。否则，可以通过调整变成这种情况并且不劣。称这些点为关键点。

此时其实可以写出一个 $O(n^4)$ dp：设 $dp_{i,j,k,l}$ 表示包含第 $i$ 个关键点的区间，设当前位置为 $x$，有 $j$ 个的 $a_i<x$，$k$ 个的 $a_i>x$，还有 $l$ 个没有确定。转移甚至可能还不是 $O(1)$ 的，但是显然不对所以就没写。

先尝试优化，可能会根据想到进行一些分讨，但是看着就不太行。于是再考虑进行转化。仔细想想，区间异或，只有若干个关键点，会想到？对了，差分！

考虑把操作和限制都转化成差分数组上的。操作变成，每次选择 $a_i$ 和任意一个位置 $\oplus 1$，限制变成，要求最后若干个位置是 $1$。于是可以得到还有若干个位置需要 $\oplus1$，而对于若干个可以任意选择的位置，要不两两匹配，要不找一个还需要 $1$ 的位置匹配。

于是把 $a_i$ 和需要 $1$ 的位置放在一起排序后 dp（话说似乎是种不同的 dp）：设 $dp_{i,j,0/1}$ 表示到了第 $i$ 个位置，当前还有 $j$ 个没有匹配，并且没有匹配的是 $a_i$/需要 $1$ 的位置。容易证明两种不会同时没有匹配，因为这样的话在前面就先匹配上更优。转移是 trivial 的，使用一些费用提前计算的技巧即可。

于是时间 $O(n^2)$，空间滚动后 $O(n)$ 通过了这题。

code：

int n,m;
ll dp[2][N][2];
pii a[N];
map<int,int> c;
void Yorushika(){
	read(n,m);
	rep(i,1,n){
		read(a[i].fi);
		c[a[i].fi]^=1;
	}
	rep(i,1,m){
		int x;read(x);
		c[x]^=1;
	}
	m=0;
	int cnt=0;
	for(auto [i,j]:c){
		cnt+=j;
		if(j){
			a[++n]=Mp(i,1);
		}
	}
	if(cnt+cnt>n){
		puts("-1");
		return;
	}
	sort(a+1,a+n+1);
	mems(dp,0x3f);
	dp[0][0][0]=0;
	rep(i,1,n){
		int p=i&1;
		mems(dp[p],0x3f);
		rep(j,1,n){
			dp[p][j-1][0]=min(dp[p][j-1][0],dp[p^1][j][0]+1ll*(a[i].fi-a[i-1].fi)*j);
		}
		rep(j,1,n){
			dp[p][j+1][1]=min(dp[p][j+1][1],dp[p^1][j][1]+1ll*(a[i].fi-a[i-1].fi)*j);
		}
		dp[p][1][1]=min({dp[p][1][1],dp[p^1][0][0],dp[p^1][0][1]});
		if(!a[i].se){
			rep(j,1,n){
				dp[p][j-1][1]=min(dp[p][j-1][1],dp[p^1][j][1]+1ll*(a[i].fi-a[i-1].fi)*j);
			}
			rep(j,1,n){
				dp[p][j+1][0]=min(dp[p][j+1][0],dp[p^1][j][0]+1ll*(a[i].fi-a[i-1].fi)*j);
			}
			dp[p][1][0]=min({dp[p][1][0],dp[p^1][0][0],dp[p^1][0][1]});
		}
	}
	printf("%lld\n",min(dp[n&1][0][0],dp[n&1][0][1]));
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}