11259: [yosupo] Graph - Strongly Connected Components (Incremental)
[Creator : ]
Description
There is a $N$ vertices and $0$ edges directed graph $G$, and an integer sequence $x_0, \ldots, x_{N-1}$.
Add $M$ directed edges to $G$. The $i$-th edge is directed from $a_i$ to $b_i$.
After adding each edge, output the remainder when $X$ defined below modulo $998244353$:
- Define $\mathrm{same}(i,j)$ as $1$ if vertices $i$ and $j$ belong to the same strongly connected component in $G$, and $0$ otherwise, for $0\leq i,j \leq N-1$.
- Define $X = \sum_{0\leq i<j\leq N-1}\mathrm{same}(i,j)x_ix_j$.
Add $M$ directed edges to $G$. The $i$-th edge is directed from $a_i$ to $b_i$.
After adding each edge, output the remainder when $X$ defined below modulo $998244353$:
- Define $\mathrm{same}(i,j)$ as $1$ if vertices $i$ and $j$ belong to the same strongly connected component in $G$, and $0$ otherwise, for $0\leq i,j \leq N-1$.
- Define $X = \sum_{0\leq i<j\leq N-1}\mathrm{same}(i,j)x_ix_j$.
Input
$N$ $M$
$x_0$ $\ldots$ $x_{N-1}$
$a_0$ $b_0$
$a_1$ $b_1$
$\vdots$
$a_{M - 1}$ $b_{M - 1}$
$x_0$ $\ldots$ $x_{N-1}$
$a_0$ $b_0$
$a_1$ $b_1$
$\vdots$
$a_{M - 1}$ $b_{M - 1}$
Constraints
- $1 \leq N \leq 5\times 10^5$
- $1 \leq M \leq 5\times 10^5$
- $0 \leq x_i < 998244353$
- $0 \leq a_i, b_i < N$
- $1 \leq M \leq 5\times 10^5$
- $0 \leq x_i < 998244353$
- $0 \leq a_i, b_i < N$
Sample 1 Input
4 6
1 1 1 1
0 1
1 2
2 0
2 3
1 3
3 0
Sample 1 Output
0
0
3
3
3
6
Sample 2 Input
4 6
12 34 56 78
0 1
1 2
2 0
2 3
1 3
3 0
Sample 2 Output
0
0
2984
2984
2984
10940
Sample 3 Input
2 7
12 34
0 0
1 1
0 0
0 1
1 1
0 1
1 0
Sample 3 Output
0
0
0
0
0
0
408