思路
对于一个数组，每次操作会缩短排序后的数组的相邻两个数的差距，所以总共会执行 \(k\) 次操作，其中，\(k\) 为排序后的数组的相邻两个数的最大差距。
因为每次操作都会对最大数加 \(1\)，所以答案就是 \(\text{数组中的最大数} + \text{排序后的数组的相邻两个数的最大差距}\)。
因为修改操作修改的位置是按照原数组的位置而定的，所以如果每次修改操作都排序一遍的话，还需要在修改前再排一遍排回去，所以时间复杂度很高，必定会 TLE。
TLE code
#include<bits/stdc++.h>
using namespace std;
struct node{long long v,id;}a[200005];
inline bool cmp(node a,node b){return a.v<b.v;}
inline bool cmp1(node a,node b){return a.id<b.id;}
long long T,n,q,x,b;
int main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&n);
for(int i=1;i<=n;++i) scanf("%lld",&a[i].v),a[i].id=i;
scanf("%lld",&q);
while(q--)
{
sort(a+1,a+n+1,cmp1);
scanf("%lld%lld",&x,&b),a[x].v=b;
sort(a+1,a+n+1,cmp);long long maxn=0;
for(long long i=1;i<n;++i) maxn=max(maxn,a[i+1].v-a[i].v);
printf("%lld ",a[n].v+maxn);
}
puts("");
}
}
我们假设修改的位置是 \(p\)，排序后这个位置的前一个位置是 \(pr\)，后一个位置是 \(ne\)。
那么，相邻两数的差就最多更改两个地方，比如：原本的 \(a[p]-a[pr]\) 与 \(a[ne]-a[p]\) 会合并为 \(a[ne]-a[pr]\)，同样会更改的地方还有改后的位置前后。
所以，我们可以考虑维护两个 \(\operatorname{multiset}\) 即可以出现重复元素的集合。
一个集合用于储存 \(a\) 数组，一个集合用于储存排序后相邻元素的差值。
然后用迭代器快速修改和查询，注意特殊情况的判断。
注：如果真的不是没有更好的方法，慎用迭代器。
AC code
#include<bits/stdc++.h>
using namespace std;
int T,n,a[200005],q,p,v;
multiset<int>s,c;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
if(n==1)//特判特殊情况
{
scanf("%d",&q);
while(q--) scanf("%d%d",&p,&v),printf("%d ",v);
puts("");
}
else
{
s.clear(),c.clear();//记得清空
for(int i=1;i<=n;++i) s.insert(a[i]);
for(auto i=++s.begin();i!=s.end();++i)
{
auto pr=i;
--pr;
c.insert(*i-*pr);
}
scanf("%d",&q);
while(q--)
{
scanf("%d%d",&p,&v);
auto i=s.find(a[p]),ne=i,pr=i;++ne,--pr;//找到对应位置以及位置前后
if(i==s.begin()) c.erase(c.find(*ne-*i));//如果在最前面，只用删除位置后一段的差值
else if(i==--s.end()) c.erase(c.find(*i-*pr));//如果在最后面，只用删除位置前一段的差值
else c.erase(c.find(*ne-*i)),c.erase(c.find(*i-*pr)),c.insert(*ne-*pr);//否则，合并位置前后的差值
s.erase(i),s.insert(v),i=s.find(v),ne=i,pr=i;++ne,--pr;//修改集合s，顺便找到对应位置及位置前后
if(i==s.begin()) c.insert(*ne-*i);//如果在最前面，只用添加位置后的差值
else if(i==--s.end()) c.insert(*i-*pr);//如果在最后面，只用添加位置前的差值
else c.insert(*ne-*i),c.insert(*i-*pr),c.erase(c.find(*ne-*pr));//否则，拆开位置前后的差值
a[p]=v;//记得修改原数组
printf("%d ",*--s.end()+*--c.end());//数组最大值+差值最大值
}
puts("");
}
}
return 0;
}
//使用迭代器会变得不幸！调了快一天了，最后还是和官方题解找不同调好的。