题解：AT_arc187_d [ARC187D] Many Easy Optimizations

你们 ARC 签到题放 D 的吗，，，

最大/小化极差的套路是枚举其中一个并最大/小另一个。那么设 f_i 表示最小值为 i 时的最小最大值，显然 f 是单调不降的，且答案是 \min\{f_i - i\}。注意如果 i 并不存在于序列中也没关系，此时 f_i - i 一定不是最优解因为调大 i 一定不劣。

考虑加入一个数对 (a,b)，令 a \le b。那么应该有下面的变化：

因为 f 是单调的，区间取 \max 可以变为区间推平。直接上 odt 就结束了，复杂度 \mathcal O(n \log n)。

/**
 *    author: sunkuangzheng
 *    created: 17.11.2024 20:33:35
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
int T,n,a[N],b[N]; vector<int> c;
struct odt{
    int l,r; mutable int v;
    odt(int al,int ar,int av){l = al,r = ar,v = av;}
    bool operator <(const odt &x)const{return l < x.l || l == x.l && r < x.r;}
}; set<odt> s; multiset<int> ans;
auto split(int x){
    auto it = s.lower_bound(odt{x,-1,0});
    if(it != s.end() && it -> l == x) return it;
    auto [l,r,v] = *(-- it);
    if(r < x) return s.end(); 
    s.erase(it);
    s.emplace(l,x-1,v),ans.insert(c[v] - c[x-1]);
    return s.emplace(x,r,v).first;
}void push(int l,int r,int v){
    auto ir = split(r + 1),il = split(l);
    if(r + 1 >= c.size()) ir = s.end();
    for(auto it = il;it != ir;it ++){
        auto [l,rr,x] = *it; if(x >= v){ir = it,r = l - 1; break;}
        ans.erase(ans.find(c[x] - c[rr]));
    }s.erase(il,ir);
    if(l <= r) s.emplace(l,r,v),ans.insert(c[v] - c[r]);
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i],c.push_back(a[i]);
    for(int i = 1;i <= n;i ++) cin >> b[i],c.push_back(b[i]);
    sort(c.begin(),c.end()),c.erase(unique(c.begin(),c.end()),c.end()),c.push_back(2e9);
    int m = c.size();
    for(int i = 0;i < m;i ++) s.emplace(i,i,i),ans.insert(0);
    ans.erase(ans.find(0));
    for(int i = 1;i <= n;i ++){
        a[i] = lower_bound(c.begin(),c.end(),a[i]) - c.begin();
        b[i] = lower_bound(c.begin(),c.end(),b[i]) - c.begin();
        if(a[i] > b[i]) swap(a[i],b[i]);
        push(0,a[i],a[i]),push(a[i] + 1,b[i],b[i]),push(b[i] + 1,m - 1,m - 1);
        cout << (*ans.begin()) << "\n";
    }
}