P17849 「RiOI-(-2)」houran 和序列 / [USACO26FEB] Milk Buckets S 加强版

houran 有一个长度为 $n$ 的正整数序列，第 $i$ 个元素为 $a_i$。 houran 想要知道这个序列所有数的乘积。但是 houran 不喜欢太大的数。具体地，houran 有一个接受的值域上限 $V$。 他会对序列进行 $m$ 单点修改操作。在所有修改操作前与每次操作过后，设所有数的乘积为 $X$： - 若 $X

第一行三个正整数 $n,m,V$。 接下来一行 $n$ 个正整数 $a_i$。 接下来 $m$ 行，每行两个数 $x,y$，表示进行了一次操作，将 $a_x$ 的值修改为 $y$。

输出一行一个整数，表示所有答案的异或和。

下发文件过大，故没有上传。 ### 【样例 $1$ 解释】 在操作二之后，序列中所有数的乘积一直大于 $V$，因此答案应为 $2\oplus3=1$。 ### 【样例 $2$】 见选手目录下的 `query/query2.in` 与 `query/query2.ans`。 该样例满足测试点 $1,2$ 的约束条件。 ### 【样例 $3$】 见选手目录下的 `query/query3.in` 与 `query/query3.ans`。 该样例满足测试点 $7\sim9$ 的约束条件。 ### 【样例 $4$】 见选手目录下的 `query/query4.in` 与 `query/query4.ans`。 该样例满足测试点 $10,11$ 的约束条件。 ### 【样例 $5$】 见选手目录下的 `query/query5.in` 与 `query/query5.ans`。 该样例满足测试点 $12,13$ 的约束条件。 ### 【样例 $6$】 见选手目录下的 `query/query6.in` 与 `query/query6.ans`。 该样例满足测试点 $14$ 的约束条件。 ### 【样例 $7$】 见选手目录下的 `query/query7.in` 与 `query/query7.ans`。 该样例满足测试点 $15\sim20$ 的约束条件。 ### 【数据范围】 对于所有测试数据，均有： - $1\le n,m\le5\times10^6$，$2\le V\le10^9$； - 对于所有 $1\le i\le n$，均有 $1\le a_i\le V$； - 对于所有修改操作，均有 $1\le x\le n$，$1\le y\le V$； ::cute-table{tuack} | 测试点编号 | $n\le$ | $m\le$ | $V\le$ | 特殊性质 | |:-:|:-:|:-:|:-:|:-:| | $1,2$ | $3000$ | $3000$ | $10^9$ | 无 | | $3$ | $5\times10^5$ | $5\times10^5$ | ^ | ^ | | $4\sim6$ | $10^6$ | $10^6$ | ^ | ^ | | $7\sim9$ | $2\times10^6$ | $2\times10^6$ | ^ | ^ | | $10,11$ | $5\times10^6$ | $5\times10^6$ | $10$ | ^ | | $12,13$ | ^ | ^ | $1000$ | ^ | | $14$ | ^ | ^ | $10^9$ | $A$ | | $15\sim20$ | ^ | ^ | ^ | 无 | 特殊性质 $A$：对于每次进行修改操作时，均有 $a_x \le y$。 **请注意常数因子对程序效率的影响。** 本题读入量巨大，我们下发了一个基于 `fread` 的快读模板。选手可以查看下发文件中的 `query/fastIO.cpp`，其中的 `read()` 函数可以用于读入一个非负整形变量。 ```cpp #include char buf[1 = '0' && c