CF1810F.M-tree

A rooted tree is called good if every vertex of the tree either is a leaf (a vertex with no children) or has exactly $m$ children.

For a good tree, each leaf $u$ has a positive integer $c_{u}$ written on it, and we define the value of the leaf as $c_{u} + \mathrm{dep}_{u}$, where $\mathrm{dep}_{u}$ represents the number of edges of the path from vertex $u$ to the root (also known as the depth of $u$). The value of a good tree is the maximum value of all its leaves.

Now, you are given an array of $n$ integers $a_{1}, a_{2}, \ldots, a_{n}$, which are the integers that should be written on the leaves. You need to construct a good tree with $n$ leaves and write the integers from the array $a$ to all the leaves. Formally, you should assign each leaf $u$ an index $b_{u}$, where $b$ is a permutation of length $n$, and represent that the integer written on leaf $u$ is $c_u = a_{b_{u}}$. Under these constraints, you need to minimize the value of the good tree.

You have $q$ queries. Each query gives you $x$, $y$ and changes $a_{x}$ to $y$, and after that, you should output the minimum value of a good tree based on the current array $a$.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

一棵有根树被称为“好树”，当且仅当该树的每个顶点要么是叶节点（即没有子节点的顶点），要么恰好有 $m$ 个子节点。

对于一棵好树，每个叶节点 $u$ 上写有一个正整数 $c_{u}$，我们定义该叶节点的值为 $c_{u} + \mathrm{dep}_{u}$，其中 $\mathrm{dep}_{u}$ 表示从顶点 $u$ 到根节点的路径上的边数（也称为 $u$ 的深度）。一棵好树的值定义为它所有叶节点的值中的最大值。

现在，你被给定一个包含 $n$ 个整数的数组 $a_{1}, a_{2}, \ldots, a_{n}$，这些整数将被写在叶节点上。你需要构造一棵具有 $n$ 个叶节点的好树，并将数组 $a$ 中的整数一一写在所有叶节点上。形式化地说，你需要为每个叶节点 $u$ 分配一个下标 $b_{u}$，其中 $b$ 是一个长度为 $n$ 的排列，使得叶节点 $u$ 上所写的整数为 $c_u = a_{b_{u}}$。在这些约束条件下，你需要使该好树的值最小化。

你将处理 $q$ 次查询。每次查询给出 $x$ 和 $y$，并将 $a_{x}$ 修改为 $y$；此后，你需要输出基于当前数组 $a$ 所能构造出的最小好树的值。

一个长度为 $n$ 的排列是指由 $1$ 到 $n$ 这 $n$ 个互不相同的整数组成的、顺序任意的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是一个排列（此时 $n = 3$，但数组中包含了 $4$）。

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

The first line contains three integers $n$, $m$, and $q$ ($1\le n,q \le 2 \cdot 10^5$, $2\le m \le 2\cdot 10^5$, $n \equiv 1 \pmod {m - 1}$) — the number of the leaves, the constant $m$, and the number of queries.

The second line contains $n$ integers $a_{1},a_{2}, \ldots, a_{n}$ ($1 \le a_{i} \le n$) — the initial array.

For the following $q$ lines, each line contains two integers $x$ and $y$ ($1\le x,y\le n$), representing a query changing $a_{x}$ to $y$.

It is guaranteed that both the sum of $n$ and the sum of $q$ do not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。随后是各测试用例的描述。

第一行包含三个整数 $n$、$m$ 和 $q$（$1\le n,q \le 2 \cdot 10^5$，$2\le m \le 2\cdot 10^5$，且满足 $n \equiv 1 \pmod {m - 1}$）—— 分别表示叶子节点的数量、常数 $m$ 以及查询次数。

第二行包含 $n$ 个整数 $a_{1},a_{2}, \ldots, a_{n}$（$1 \le a_{i} \le n$）—— 初始数组。

接下来的 $q$ 行中，每行包含两个整数 $x$ 和 $y$（$1\le x,y\le n$），表示一次将 $a_{x}$ 修改为 $y$ 的查询。

保证所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $2\cdot 10^5$。

For each test case, output $q$ integers in one line, the $i$-th of which is the minimum tree value after the $i$-th change.

对于每个测试用例，在一行中输出 $q$ 个整数，其中第 $i$ 个整数表示经过第 $i$ 次修改后的最小树值。

In the first test case, after the first query, the current array $a$ is $[4,3,4,4,5]$. We can construct such a good tree:

The first number inside a vertex is its index (in this problem, the indices do not matter, but help to understand the figure). If a vertex is a leaf, the second number inside the vertex is the integer written on it.

We can tell that $\mathrm{dep}_{3}=\mathrm{dep}_{4}=1,\mathrm{dep}_{5}=\mathrm{dep}_{6}=\mathrm{dep}_{7}=2$ and the value of the tree, which is the maximum value over all leaves, is $5+1=6$. The value of leaves $5$, $6$, $7$ is also equal to $6$. It can be shown that this tree has the minimum value over all valid trees.

在第一个测试用例中，第一次查询后，当前数组 $a$ 为 $[4,3,4,4,5]$。我们可以构造如下一棵“好树”：

顶点内部的第一个数字是其索引（本题中索引并不重要，但有助于理解图示）。若某顶点为叶子节点，则其内部的第二个数字即为写在该叶子上的整数。

我们可以得出：$\mathrm{dep}_{3}=\mathrm{dep}_{4}=1$，$\mathrm{dep}_{5}=\mathrm{dep}_{6}=\mathrm{dep}_{7}=2$；而该树的值（即所有叶子节点对应值中的最大值）为 $5+1=6$。叶子节点 $5$、$6$、$7$ 的值也均为 $6$。可以证明，该树在所有合法树中具有最小的值。