CF1810F.M-tree
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 cu written on it, and we define the value of the leaf as cu+depu , where depu 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 a1,a2,…,an , 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 bu , where b is a permutation of length n , and represent that the integer written on leaf u is cu=abu . 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 ax 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).
输入格式
Each test contains multiple test cases. The first line contains a single integer t ( 1≤t≤104 ) — the number of test cases. Their description follows.
The first line contains three integers n , m , and q ( 1≤n,q≤2⋅105 , 2≤m≤2⋅105 , n≡1(modm−1) ) — the number of the leaves, the constant m , and the number of queries.
The second line contains n integers a1,a2,…,an ( 1≤ai≤n ) — the initial array.
For the following q lines, each line contains two integers x and y ( 1≤x,y≤n ), representing a query changing ax to y .
It is guaranteed that both the sum of n and the sum of q do not exceed 2⋅105 .
输出格式
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.
输入输出样例
输入#1
3 5 3 3 3 3 4 4 5 1 4 2 4 3 5 5 2 4 3 3 4 4 5 1 4 2 5 3 5 4 5 7 3 4 1 2 2 3 3 3 4 1 4 2 1 5 5 6 6
输出#1
6 6 6 7 7 7 8 6 6 6 7
说明/提示
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 dep3=dep4=1,dep5=dep6=dep7=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.