区间连边并查集

【题目描述】

有一个包含 $N$ 个顶点且没有边的无向图 $G$，以及一个整数序列 $x_0, \ldots, x_{N-1}$。请处理 $Q$ 个如下形式的查询：

• $k$ $a$ $b$：对于每个 $i=0,1,\ldots,k-1$，向 $G$ 中添加边 $(a+i,b+i)$。

处理每个查询后，输出下述定义的 $X$ 对 $998244353$ 取模后的余数：

• 如果顶点 $i$ 和顶点 $j$ 属于同一个连通块，则定义 $\mathrm{same}(i,j)=1$，否则定义 $\mathrm{same}(i,j)=0$，其中 $0\leq i,j \leq N-1$。
• 定义 $X = \sum_{0\leq i<j\leq N-1}\mathrm{same}(i,j)x_ix_j$。

【输入】

输入包含：

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

【输出】

对于每个查询，输出一行 $X$ 对 $998244353$ 取模后的余数。

【输入样例】

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

【输入样例2】

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

【输出样例2】

0
0
672
10940
10940
10940
27140

【数据范围】

• $1 \leq N \leq 500000$
• $1 \leq Q \leq 500000$
• $0 \leq x_i < 998244353$
• $0 \leq k\leq N$
• $0 \leq a,b \leq N-k$

【来源】

Library Checker（yosupo06） range_parallel_unionfind