Simultaneous Coloring

· 2024-08-18 · # Codeforces # 题解

给你一个 $n\times m$ 的矩阵，你可以将一行染成红色，或者将一列染成蓝色。依次的染色不需要代价，如果 $k$ 行或者列一起染色，就需要花费 $k^2$ 的代价，但是你可以选择在相交的地方保留哪一种颜色。

有 $q$ 个询问，要求 $(x_i,y_i)$ 的颜色为 $c_i$ 和前面所有的询问的要求都满足的代价的总和的最小值。

其中数据范围满足， $1\le n,m,q\le 2\times 10^5$ 。

考虑用图论的方法求解。

如果要求 $(x,y)$ 为蓝色，那么将 $x$ 行向 $y$ 列连边，表示 $x$ 被染色的时间不晚于 $y$ 。同样的，如果要求 $(x,y)$ 为红色，那么将 $y$ 列向 $x$ 行连边，表示 $y$ 被染色的时间不晚于 $x$ 。

如果这样联出的图有强连通分量，那么这个前联通分量一定需要一起染色，所以代价就是强连通分量大小平方的和。

考虑对事件分治，假设现在考虑的是 $[l,r]$ ，那么如果在 $[l,r]$ 中是强连通分量就一定在 $[mid+1,r]$ 中也是，所以在求解 $[mid+1,r]$ 时就不用考虑。

而如果一条边在 $[l,r]$ 中是不是强连通分量，那么在 $[l,mid]$ 中也同样不用考虑。