构造、贪心、二分

已知 $a_i + d_{i}^{\min}$ 在 $b$ 中出现，考虑怎么得到 $d_{i}^{\min}$ 的值。

最优情况自然是 $b_1=a_i + d_{i}^{\min}$，但是有可能 $a_i > b_1$，所以二分出第一个不小于 $a_i$ 的元素 $b_j$ 即可得到 $d_{i}^{\min} = b_j - a_i$。

接下来考虑怎么得到 $d_{i}^{\max}$ 的值。最优情况为 $b_n=a_i + d_{i}^{\max}$。但如果 $a_i + d_{i}^{\max} = b_j$ 则需要让所有 $a_k(k \in [i+1,j])$ 能对应 $b_{k-1}$，否则 $a_i$ 无法对应到 $b_j$。

如果 $a_k \leq b_{k-1}$ 那么能够对应，这部分可以用前缀和加二分维护以得到最大的满足 $a_k(k \in [i+1,j])$ 都能和 $b_{k-1}$ 对应的 $j$ 的值。

时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
int n,a[200'005],b[200'005],sum[200'005];
void solution(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) cout<<*lower_bound(b+1,b+n+1,a[i])-a[i]<<" \n"[i==n];
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+(a[i]<=b[i-1]);
    for(int i=1;i<=n;i++){
        int l=i,r=n,ans=i;
        while(l<=r){
            int mid=(l+r)>>1;
            if(sum[mid]-sum[i]!=mid-i) r=mid-1;
            else ans=mid,l=mid+1;
        }
        cout<<b[ans]-a[i]<<" \n"[i==n];
    }
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}