关于边分治的卡常建议
查看原帖
关于边分治的卡常建议
353688
王熙文楼主2023/8/1 00:05

在维护所有边的路径最大值的集合(堆)中,一次修改会先删除边的贡献,后插入新修改后边的贡献,此时如果两次贡献相等,就不需要先删除后插入了。

比如下面这个代码:

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);
				}
			}
2023/8/1 00:05
加载中...