区间并查集（Range Parallel Unionfind）

问题描述

给定一个含 $N$ 个顶点、0 条边的无向图 $G$，以及一个整数序列 $x_0, \dots, x_{N-1}$。请处理以下 $Q$ 个查询：

• k a b：对每个 $i = 0, 1, \dots, k-1$，添加一条边 $(a+i, b+i)$。

每次查询处理完毕后，输出下式模 $998244353$ 的余数：

• 定义 $\text{same}(i,j) = \begin{cases} 1 & \text{若 } i,j \text{ 属于 } G \text{ 的同一连通分量} \\ 0 & \text{否则} \end{cases}$，其中 $0 \le i,j \le N-1$；
• 定义 $X = \sum_{0 \le i < j \le N-1} \text{same}(i,j) \cdot x_i x_j$。

约束条件

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq Q \leq 5 \times 10^5$
• $0 \leq x_i < 998244353$
• $0 \leq k \leq N$
• $0 \leq a, b \leq N - k$

输入格式

$N\ Q$
$x_0\ \cdots\ x_{N-1}$
$k\ a\ b$
:
$k\ a\ b$

5 7
1 1 1 1 1
0 0 0
1 0 0
1 0 2
2 2 1
2 0 1
4 0 0
3 2 1

0
0
1
6
6
6
10

5 7
12 34 56 78 90
0 0 0
1 0 0
1 0 2
2 2 1
2 0 1
4 0 0
3 2 1

0
0
672
10940
10940
10940
27140