Codeforces Round 894 G

玩一下样例就能知道 这个是和 每个seg的最大间隔相关
为了好写我们可以直接写成元素间隔
这样我们用两个multiset维护元素间隔以及元素即可
注意删除的时候我们只删一个值 需要删指针
还有考虑长度为1的情况

multiset<int>st,st1;
void Erase(int x){
    auto it=st1.lower_bound(x);
    st1.erase(it);
}
void solve(){
    st.clear();st1.clear();
    int n;cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        st.insert(a[i]);
    }
    int pre=-1;
    for(auto i:st){
        if(pre!=-1)st1.insert(i-pre);
        pre=i;
    }
    int q;cin>>q;
    while(q--){
        int pos,x;cin>>pos>>x;
        if(n==1){
            a[1]=x;
            cout<<a[1]<<' ';
            continue;
        }
        auto it=st.lower_bound(a[pos]);
        if(it!=st.begin()&&it!=prev(st.end())){
            auto itl=prev(it);
            auto itr=next(it);
            Erase(*it-*itl);
            Erase(*itr-*it);
            st1.insert(*itr-*itl);
        }else if(it!=st.begin()){
            auto itl=prev(it);
            Erase(*it-*itl);
        }else if(it!=prev(st.end())){
            auto itr=next(it);
            Erase(*itr-*it);
        }
        auto ii=st.lower_bound(a[pos]);
        st.erase(ii);
        a[pos]=x;
        st.insert(a[pos]);
        it=st.lower_bound(a[pos]);
        if(it!=st.begin()&&it!=prev(st.end())){
            auto itl=prev(it);
            auto itr=next(it);
            st1.insert(*it-*itl);
            st1.insert(*itr-*it);
            Erase(*itr-*itl);
        }else if(it!=st.begin()){
            auto itl=prev(it);
            st1.insert(*it-*itl);
        }else if(it!=prev(st.end())){
            auto itr=next(it);
            st1.insert(*itr-*it);
        }
        cout<<*st1.rbegin()+*st.rbegin()<<' ';
    }cout<<endl;
}