在维护所有边的路径最大值的集合(堆)中,一次修改会先删除边的贡献,后插入新修改后边的贡献,此时如果两次贡献相等,就不需要先删除后插入了。
比如下面这个代码:
for(Belong j:vec[x])
{
int lst;
if(!st[j.ed][0].empty() && !st[j.ed][1].empty()) lst=st[j.ed][0].get_max()+st[j.ed][1].get_max();
else lst=1e9;
if(vis[x]) st[j.ed][j.op].del(j.dis);
else st[j.ed][j.op].insert(j.dis);
int now;
if(!st[j.ed][0].empty() && !st[j.ed][1].empty()) now=st[j.ed][0].get_max()+st[j.ed][1].get_max();
else now=1e9;
if(lst!=now)
{
if(lst!=1e9) allst.del(lst);
if(now!=1e9) allst.insert(now);
}
}