F-Connected Graph_牛客练习赛151

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\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}$ 单独的点也构成一个连通块。

输入描述:

第一行输入四个正整数 ，表示初始序列长度，加法条件的取模基数，乘法条件的阈值，修改操作的次数。
第二行输入  个正整数 ，表示序列的初始值。
此后  行，第  行输入两个正整数 ，表示将序列中第  个位置的值修改为 。

输出描述:

对于每一次询问，请参考下方的格式输出：
第一行输出一个整数，表示序列在初始状态下图中连通块的数量。
此后  行，第  行输出一个整数，表示第  次修改操作后图中连通块的数量。

示例1

输入

复制

10 20 50 5
2 3 5 8 12 15 20 25 30 35
5 10
1 100
6 5
10 5
2 40

输出

复制

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。