区间AI (CI翻译)
There are $n$ positions numbered from $1$ to $n$.
有 $n$ 个位置，编号为 $1$ 到 $n$。AI (CI翻译)
For every interval $[l,r]$, where $1 \le l \le r \le n$, there is a value associated with this interval. Values can be obtained in the following ways:
对于每个满足 $1 \le l \le r \le n$ 的区间 $[l,r]$，都有一个与之关联的值。可以通过以下方式获得这些值：AI (CI翻译)
- You may choose any interval
$[l,r]$and obtain its value directly. This costs one direct query. - If, for some
$k$with$l \le k \lt r$, you have already obtained the values for$[l,k]$and$[k+1,r]$, then you may combine them and obtain the value for$[l,r]$for free.
- 你可以选择任意区间
$[l,r]$，直接查询并获得它的值。这会消耗一次直接查询。 - 对于某个满足
$l \le k \lt r$的$k$，如果你已经获得了$[l,k]$和$[k+1,r]$的值，那么可以将它们合并，免费获得$[l,r]$的值。
You may use the second operation any number of times. Values cannot be split: knowing the value for $[l,r]$ does not give you the values for its subintervals. There are no other ways to obtain values.
你可以使用第二种操作任意多次。值不能拆分：知道 $[l,r]$ 的值，并不能让你获得其子区间的值。除此之外，没有其他获得值的方式。AI (CI翻译)
At any moment, there are $m$ required intervals. Your task is to determine the minimum number of direct queries needed to obtain the values for all required intervals.
在任意时刻，都有 $m$ 个需要求值的区间。你的任务是确定获得所有这些区间的值所需的最少直接查询次数。AI (CI翻译)
After the initial configuration, $q$ modifications are performed. Each modification replaces one required interval with a new interval. You must output the answer for the initial configuration and after each modification.
在初始配置之后，会进行 $q$ 次修改。每次修改将一个需要求值的区间替换为一个新区间。你需要输出初始配置以及每次修改后的答案。AI (CI翻译)
Each configuration is considered independently. That is, for every output value, you need the minimum number of direct queries needed starting with no values already obtained.
每个配置都独立考虑。也就是说，对于每个输出的答案，你都需要求出在尚未获得任何值的情况下，所需的最少直接查询次数。AI (CI翻译)
Input
输入格式
AI (CI翻译)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.
每个测试包含多组测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是各组测试用例的描述。AI (CI翻译)
The first line of each test case contains three integers $n$, $m$, and $q$ ($1 \le n,m,q \le 2\cdot 10^5$) — the number of positions, the number of required intervals, and the number of modifications.
每组测试用例的第一行包含三个整数 $n$、$m$ 和 $q$ ($1 \le n,m,q \le 2\cdot 10^5$)——分别表示位置的数量、需要求值的区间数量以及修改次数。AI (CI翻译)
The next $m$ lines contain two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$). They describe the initial required intervals.
接下来的 $m$ 行，每行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le n$)，描述初始时需要求值的区间。AI (CI翻译)
The next $q$ lines contain three integers $p$, $l$, and $r$ ($1 \le p \le m$, $1 \le l \le r \le n$). The required interval with index $p$ is replaced by $[l,r]$.
接下来的 $q$ 行，每行包含三个整数 $p$、$l$ 和 $r$ ($1 \le p \le m$，$1 \le l \le r \le n$)。编号为 $p$ 的需要求值的区间被替换为 $[l,r]$。AI (CI翻译)
It is guaranteed that the sums of $n$, $m$, and $q$ over all test cases do not exceed $2\cdot 10^5$ each.
保证所有测试用例的 $n$ 之和、$m$ 之和以及 $q$ 之和分别不超过 $2\cdot 10^5$。AI (CI翻译)
Output
输出格式
AI (CI翻译)For each test case, print $q+1$ integers, each on a separate line.
对于每组测试用例，输出 $q+1$ 个整数，每个整数占一行。AI (CI翻译)
The first integer must be the minimum number of direct queries needed for the initial configuration. Then, after each modification, print the minimum number of direct queries needed for the current configuration.
第一个整数应为初始配置所需的最少直接查询次数。然后，在每次修改后，输出当前配置所需的最少直接查询次数。AI (CI翻译)
Note
说明
AI (CI翻译)In the first test case, initially at least $3$ direct queries are needed, so the answer is $3$.
在第一组测试用例中，初始时至少需要 $3$ 次直接查询，因此答案为 $3$。AI (CI翻译)
After the first modification, the required intervals are $[1,2]$, $[3,5]$, and $[1,5]$. We can query $[1,2]$ and $[3,5]$ directly, and combine them to obtain $[1,5]$. Therefore, only $2$ direct queries are needed.
第一次修改后，需要求值的区间为 $[1,2]$、$[3,5]$ 和 $[1,5]$。我们可以直接查询 $[1,2]$ 和 $[3,5]$，再将它们合并得到 $[1,5]$。因此，只需要 $2$ 次直接查询。AI (CI翻译)
After the second modification, the required intervals are $[2,2]$, $[3,5]$, and $[1,5]$. At least $3$ direct queries are needed, so the answer is $3$.
第二次修改后，需要求值的区间为 $[2,2]$、$[3,5]$ 和 $[1,5]$。至少需要 $3$ 次直接查询，因此答案为 $3$。AI (CI翻译)
After the third modification, the required intervals are $[2,2]$, $[4,5]$, and $[1,5]$. Again, at least $3$ direct queries are needed, so the answer is $3$.
第三次修改后，需要求值的区间为 $[2,2]$、$[4,5]$ 和 $[1,5]$。同样，至少需要 $3$ 次直接查询，因此答案为 $3$。AI (CI翻译)
In the second test case, the two initial required intervals are identical, so one direct query is enough and the answer is $1$.
在第二组测试用例中，初始时需要求值的两个区间完全相同，因此一次直接查询就足够了，答案为 $1$。AI (CI翻译)
After each modification, at least $2$ direct queries are needed, so the answers are both $2$.
每次修改后，都至少需要 $2$ 次直接查询，因此两次的答案均为 $2$。AI (CI翻译)
样例
3
5 3 3
1 2
3 5
2 4
3 1 5
1 2 2
2 4 5
3 2 2
1 3
1 3
2 1 1
1 2 3
15 8 8
15 15
13 14
10 10
8 12
8 15
15 15
15 15
14 14
1 3 3
8 10 12
4 12 14
6 13 15
6 7 11
8 10 12
3 1 3
5 11 12
3
2
3
3
1
2
2
5
6
6
7
7
8
8
8
8
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。