agc036_d

agc036_d

基于题解

关于为什么没有孤立点：

注意原边不能被删去，所以孤立点并不是真正的不可到达。

如果孤立点向前面的点有连边（正边），且正边构成负环，那么一定会将正边删去，而将这个孤立点加入前面的那个区间不会新增负边，即不会有新的可能的负环，还可以保留一条向后面区间的边，所以一定不劣。

关于前缀和：

注意到正边是保留一段区间，而原来的连边不是一个矩形，所以将顺序换一下，即 $a_{i,j} \to a_{j,i}$ ，这样区间 $[i,j]$ 内的连边就是 $a_{j,j} \to a_{i,i}$ 的矩形内的连边。