Description：

给定一张 $n$ 个点 $m$ 条边的网格图，每个点有颜色。每个点只能沿着这 $m$ 条边往右往上走，问每个点能到的所有点中有多少种不同的颜色。保证 $1$ 可以到达每个点且每个点都可以到达 $n$ 。

$1\leqslant n\leqslant 300000$

Solution：

从 $n$ 开始首先到了一个点先尽量往下走，得到一个 $dfs$ 序 $dfn_1$ ，然后再尽量往左走，的到另一个 $dfs$ 序 $dfn_2$ ，那么有一个结论是从 $x$ 可以到达 $y$ 当且仅当 $dfn_1[x]\geqslant dfn_1[y]\land dfn_2[x]\geqslant dfn_2[y]$ ，于是我们按照 $dfn_2$ 的顺序考虑每个点，对于每种颜色 $i$ ，维护 $f_i$ 表示 $dfn_2$ 不超过当前点的点中颜色为 $i$ 的店的 $dfn_1$ 的最小值，那么这个可以用树状数组维护并支持快速查前缀和。

Code：

没有代码