CF2201D.Binary Not Search and Queries

For a sequence $b$ consisting of $m$ integers, the set $S(b)$ is defined as the set of tuples $(i,j,k)$ that satisfy the following conditions:

• $i$, $j$, $k$ are integers;
• $1 \le k \lt m$;
• $1 \le i \lt j \le m-k+1$;
• For every element $v$ in $b$, $v$ appears the same number of times in $[b_i,b_{i+1},\ldots,b_{i+k-1}]$ and $[b_j,b_{j+1},\ldots,b_{j+k-1}]$.

For example, when $b=[1,2,1,2]$, the tuple $(1,3,2)$ is an element of $S(b)$ because $1$ and $2$ both appear once in $[b_1,b_2]$ and $[b_3,b_4]$.

Additionally, we define two functions over sequences of positive integers:

• k_\max(b) is defined as the maximum value of $k$ over all elements $(i,j,k)$ of $S(b)$;
• $f(b)$ is defined as the number of different elements $(i,j,k)$ of $S(b)$ such that k=k_\max(b).

Exceptionally, when the set $S(b)$ is empty, they are defined as k_\max(b)=0 and $f(b)=0$.

You are given a sequence $a$ of $n$ integers. Please answer $q$ queries of the following kind:

• $i\;x$: Change the value of $a_i$ to $x$. Then, find the values of k_\max(a) and $f(a)$.

Do note that the updates are persistent. In other words, the update from one query affects the later queries as well.

对于一个由 $m$ 个整数组成的序列 $b$，集合 $S(b)$ 定义为满足以下条件的所有三元组 $(i,j,k)$ 构成的集合：

• $i$、$j$、$k$ 均为整数；
• $1 \le k \lt m$；
• $1 \le i \lt j \le m-k+1$；
• 对于 $b$ 中的每个元素 $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)$ 的值。

请注意，这些更新是持久化的。换言之，前一个查询所执行的更新会影响后续所有查询。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($2 \le n \le 200\,000$, $1 \le q \le 100\,000$).

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le n$).

Each of the following $q$ lines contains two integers $i_j$ and $x_j$ denoting the $j$-th query ($1 \le i_j,x_j \le n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $200\,000$.

It is guaranteed that the sum of $q$ over all test cases does not exceed $100\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output $q$ lines.

On the $j$-th line, you must output the values of k_\max(a) and $f(a)$ for the $j$-th query.

It can be shown that both values will never exceed $10^{11}$ under the constraints of this problem.

对于每个测试用例，输出 $q$ 行。

在第 $j$ 行中，你必须输出第 $j$ 个查询对应的 k_\max(a) 和 $f(a)$ 的值。

可以证明，在本题的约束条件下，这两个值均不会超过 $10^{11}$。

Immediately after the first query of the second test case, $a=[1,2,1,2]$. The elements of the set $S(a)$ are as follows:

• $(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}]$.

Therefore, k_\max(a)=2, and $f(a)=3$ because there are three elements $(i,j,k)$ where k=k_\max(a)=2.

Immediately after the second query of the third test case, $a=[1,3,2,4,5]$. The set $S(a)$ is empty at this point.

By definition, you should output k_\max(a)=0 and $f(a)=0$ because $S(a)$ is currently empty.

在第二个测试用例的第一个查询操作后，$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，且由于存在三个满足 k=k_\max(a)=2 的三元组 $(i,j,k)$，故 $f(a)=3$。

在第三个测试用例的第二个查询操作后，$a=[1,3,2,4,5]$。此时集合 $S(a)$ 为空。

根据定义，由于 $S(a)$ 当前为空，应输出 k_\max(a)=0 和 $f(a)=0$。