CF2201D Binary Not Search and Queries

对于一个由 $m$ 个整数构成的序列 $b$，定义集合 $S(b)$ 为满足以下条件的三元组 $(i, j, k)$ 的集合： - $i、j、k$ 为整数； - $1 \le k < m$； - $1 \le i < j \le m - k + 1$； - 对于 $b$ 中的每个元素 $v$，$v$ 在 $[b_i, b_{i+1},\ldots,b_{i+k-1}]$ 和 $[b_j, b_{j+1},\ldots,b_{j+k-1}]$ 中出现的次数相同。 例如，当 $b=[1,2,1,2]$ 时，三元组 $(1,3,2)$ 属于 $S(b)$，因为 $1$ 和 $2$ 在 $[b_1,b_2]$ 和 $[b_3,b_4]$ 中都各出现了一次。 另外，定义两个函数，作用于正整数序列： - $k_{\max}(b)$ 表示 $S(b)$ 中所有元素 $(i, j, k)$ 的 $k$ 的最大值； - $f(b)$ 表示 $S(b)$ 中所有 $k=k_{\max}(b)$ 的不同三元组 $(i, j, k)$ 的数量。 特别地，当集合 $S(b)$ 为空时，规定 $k_{\max}(b)=0$ 且 $f(b)=0$。 现在给定一个长度为 $n$ 的整数序列 $a$，请你回答 $q$ 个如下查询： - $i\;x$ ：将 $a_i$ 的值改为 $x$，然后计算 $k_{\max}(a)$ 与 $f(a)$。 请注意，更新是持续的，即一次查询中的更改会影响后续的查询。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 200\,000$，$1 \le q \le 100\,000$）。 每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le n$）。 接下来的 $q$ 行每行包含两个整数 $i_j$ 和 $x_j$，表示第 $j$ 个查询（$1 \le i_j, x_j \le n$）。 保证所有测试用例中的 $n$ 之和不超过 $200\,000$。 保证所有测试用例中的 $q$ 之和不超过 $100\,000$。

对于每个测试用例，输出 $q$ 行。 第 $j$ 行输出第 $j$ 次查询后 $a$ 的 $k_{\max}(a)$ 和 $f(a)$ 值。 保证在本题的约束下，这两个值均不会超过 $10^{11}$。

在第二个测试用例第一次查询后，$a=[1,2,1,2]$。此时 $S(a)$ 的元素如下： - $(1,3,1)$：$[\color{red}{1},2,\color{blue}{1},2]$； - $(2,4,1)$：$[1,\color{red}{2},1,\color{blue}{2}]$； - $(1,2,2)$：$[\color{red}{1},\color{magenta}{2},\color{blue}{1},2]$； - $(1,3,2)$：$[\color{red}{1},\color{red}{2},\color{blue}{1},\color{blue}{2}]$； - $(2,3,2)$：$[1,\color{red}{2},\color{magenta}{1},\color{blue}{2}]$。 因此，$k_{\max}(a)=2$，$f(a)=3$，因为存在三个三元组 $(i,j,k)$ 满足 $k=k_{\max}(a)=2$。 在第三个测试用例第二次查询后，$a=[1,3,2,4,5]$，此时 $S(a)$ 为空。 据定义，此时应输出 $k_{\max}(a)=0$ 和 $f(a)=0$，因为 $S(a)$ 目前为空。 由 ChatGPT 5 翻译