玩一下样例就能知道 这个是和 每个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;
}