Description：

给出一张有向图，要求支持加边，每个点有两个权值 $a,b$ ，维护所有可达点对 $i\to j$ 的 $a_i\times b_j$ 的和。

$1\leqslant n\leqslant1000$

Solution：

发现每次点对只会增加不会减少，因此如果能够每次加边快速找出新产生的可达点对，就可以均摊 $O(n^2)$ 的计算，设 $f(a)$ 表示从 $a$ 出发可以到达的点的集合， $g(a)$ 表示可以到达 $a$ 的点的集合，假如这次连的边为 $a\to b$ ，新增的点对为 $p\to q$ ，那么显然 $p\in g(a),p\not \in g(b)\Rightarrow p\in \complement_{g(a)}g(b)$ ，然后这些 $p$ 显然都可以通过边 $a\to b$ 到达一些新的点，枚举 $p$ ，同理 $q\in \complement_{f(b)}f(p)$ ，于是暴力计算就行了，时间复杂度 $O(n^3/w)$ 。

Code：

没有代码