A16850 | 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}$。