Connected Graph_

$\hspace{15pt}$ 给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$ （下标从 $1$ 开始），以及两个正整数 $m$ 和 $k$ 。

$\hspace{15pt}$ 我们定义一张由 $n$ 个顶点构成的无向图。对于图中的任意两个不同顶点 $i$ 和 $j$ ，它们之间存在一条无向边，当且仅当满足以下两个条件至少其中之一：
$\hspace{23pt}\bullet\,$ $(a_i + a_j) \bmod m = 0$ ；
$\hspace{23pt}\bullet\,$ $a_i \times a_j \le k$ 。
$\hspace{15pt}$ 现给定 $q$ 次单点修改操作，每次操作指定两个整数 $p$ 和 $x$ ，表示将序列中第 $p$ 个元素的值修改为 $x$ （即 $a_p = x$ ）。
$\hspace{15pt}$ 你需要计算并输出在初始状态下以及每次修改操作之后，该无向图的连通块总数。

【名词解释】
$\hspace{15pt}$ 连通块：也称连通分量，满足，
$\hspace{23pt}\bullet\,$ 是原图的一个子图；
$\hspace{23pt}\bullet\,$ 连通块内的任意两个顶点之间都存在路径相连，且路径上的点也在连通块内；
$\hspace{23pt}\bullet\,$ 是极大的，即不能再通过添加原图中的其他顶点而依旧保持连通性；
$\hspace{15pt}$ 单独的点也构成一个连通块。

$\hspace{15pt}$ 第一行输入四个正整数 $n, m, k, q \left(1 \le n, q, m \le 10^5;\, 1 \le k \le 10^6 \right)$ ，表示初始序列长度，加法条件的取模基数，乘法条件的阈值，修改操作的次数。
$\hspace{15pt}$ 第二行输入 $n$ 个正整数 $a_1, a_2, \dots, a_n \left(1 \le a_i \le 10^5 \right)$ ，表示序列的初始值。
$\hspace{15pt}$ 此后 $q$ 行，第 $i$ 行输入两个正整数 $p_i, x_i \left(1 \le p_i \le n;\, 1 \le x_i \le 10^5 \right)$ ，表示将序列中第 $p_i$ 个位置的值修改为 $x_i$ 。

$\hspace{15pt}$ 对于每一次询问，请参考下方的格式输出：
$\hspace{23pt}\bullet\,$ 第一行输出一个整数，表示序列在初始状态下图中连通块的数量。
$\hspace{23pt}\bullet\,$ 此后 $q$ 行，第 $i$ 行输出一个整数，表示第 $i$ 次修改操作后图中连通块的数量。

Connected Graph

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

相关试题