提供一个考场思路。

分析

子任务 $1$：$N \le 100$

两个多重集完全等价时，需要的操作次数即为 $\sum\limits_{i=1}^n a_i - b_i$。

几乎等价的条件允许了 $a$ 中有一个元素不进行操作，即存在一对 $a_i,b_j$ 不同，去掉后剩下的序列有解，即一一对应的 $a \ge b$。答案为满足条件的 $a_i - b_j$ 最大值。

对于每个前缀序列排序后询问，枚举 $a_i,b_j$，$O(n)$ 判断剩下的是否可行，总体时间复杂度 $O(n^4)$。

子任务 $2$：$N \le 500$

同样的对于每个前缀序列排序后询问。

$j=i$ 时必定有解，且 $j > i$ 时答案一定没有 $j=i$ 时优秀，所以只考虑 $j \le i$。

选择对于位置在 $j$ 之前的和位置在 $i$ 之后的都是没有影响的，只需要考虑这两段序列的大小关系，即 $\forall x \in [j,i), a_x \ge b_{x+1}$。

固定 $i$ 的同时依次从右向左扫描 $j$ 判断条件的同时计算最大值，时间复杂度 $O(n^2)$。总体时间复杂度 $O(n^3)$。

子任务 $3$：$N \le 3000$

同样的对于每个前缀序列排序后询问。

为了让 $a_i - b_j$ 尽可能大，$i-j$ 也要尽可能的大。

所以找到每一个满足 $a_x \ge b_{x+1}$ 的极长区间，所有极长区间答案的最大值一定是最大的，$O(n)$ 扫一遍即可。

总体时间复杂度 $O(n^2 \log n)$ 或 $O(n^2)$，取决于排序方式。

子任务 $4$：$a_i < b_{i+1}$

根据限制得到 $b_i \le a_i < b_{i+1} \le a_{i+1}$，保证前缀序列有序，无需再排序。

极长区间即为 $[1,i)$，最大值为 $a_i - b_1$，时间复杂度 $O(n)$。

子任务 $5$：$a_i \le a_{i+1}, b_i \le b_{i+1}$

保证前缀序列有序，无需再排序。

但该子任务并没有保证极长区间。

只需要维护和当前 $i$ 相连的极长区间端点 $b$ 值，新添加的 $a$ 和端点相减更新答案，时间复杂度 $O(n)$。

综合以上可以获得 $80$ 分。

//the code is from chenjh
#include<bits/stdc++.h>
#define MAXN 1000005
using namespace std;
typedef long long LL;
int n;
int a[MAXN],b[MAXN];
void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	LL ans=0;//完全等价的代价。
	int ret=0,la,lb=1;//分别表示
	for(int i=1;i<=n;i++){
		ans+=a[i]-b[i];
		if(i>1&&a[i]>=a[i-1]&&b[i]>=b[i-1]){//已经有序则无需排序。
			a[i-1]<b[i]&&(lb=max(lb,i));//不满足条件，更新极长区间起点。
			ret=max(ret,a[i]-b[lb]);
		}
		else{
			inplace_merge(a+1,a+i,a+i+1),inplace_merge(b+1,b+i,b+i+1);//懒得手写排序，所以直接归并。
			la=lb=ret=0;
			for(int j=i;j>0;--j)
				(j>=i||a[j]<b[j+1])&&(la=a[j]),ret=max(ret,la-b[j]),a[j-1]<b[j]&&(lb=max(lb,j));
		}
		printf("%lld ",ans-ret);
	}
	putchar('\n');
}
int main(){
	int T;scanf("%d",&T);
	while(T--) solve(); 
	return 0;
}

子任务 $6$：无特殊限制。

考试时败在了最后 $20$ 分。

考虑将每个极长区间表示为 $[b,a]$ 的区间。

如果两个区间有交集，则可以合并为同一个区间。

证明是容易的，如果区间 $[b_1,a_1]$ 和 $[b_2,a_2]$ 有交必然有 $a_1 \ge b_2$ 或 $a_2 \ge b_1$，即边界满足条件可以进行合并。

如果区间被已有区间完全包含，就不必合并，也不必加入，因为不会产生更大的答案。

所求为所有区间的长度最大值。

于是直接用 std::set 维护区间，时间复杂度 $O(n \log n)$。

代码

//the code is from chenjh
#include<bits/stdc++.h>
#define MAXN 1000005
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int n;
int a[MAXN],b[MAXN];
void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	LL ans=0;
	int ret=0;
	set<PII> S;
	for(int i=1;i<=n;i++){
		ans+=a[i]-b[i];
		PII c(b[i],a[i]);
		bool fl=1;
		while(!S.empty()){
			auto it=S.lower_bound(c);
			if(it!=S.end()&&it->first==c.first&&it->second>=c.second){fl=0;break;}//区间被完全包含，合并后不产生贡献，退出。
			if(it!=S.begin()&&prev(it)->second>=c.second&&prev(it)->first<=c.first){fl=0;break;}
			if(it!=S.end()&&it->first<=c.second)
				c.second=max(c.second,it->second),S.erase(it);//向右侧合并。
			else if(it!=S.begin()&&(--it)->second>=c.first)
				c.first=min(c.first,it->first),S.erase(it);//向左侧合并。
			else break;//没有区间有交集了，退出。
		}
		if(fl) S.insert(c),ret=max(ret,c.second-c.first);
		printf("%lld ",ans-ret);
	}
	putchar('\n');
}
int main(){
	int T;scanf("%d",&T);
	while(T--) solve(); 
	return 0;
}