【2019浙江省赛 - A】Vertices in the Pocket（权值线段树下二分，图，思维）

【2019浙江省赛 - A】Vertices in the Pocket（权值线段树下二分，图，思维）

题干：

DreamGrid has just found an undirected simple graph with  vertices and no edges (that's to say, it's a graph with  isolated vertices) in his right pocket, where the vertices are numbered from 1 to . Now he would like to perform  operations of the following two types on the graph:

1 a b -- Connect the -th vertex and the -th vertex by an edge. It's guaranteed that before this operation, there does not exist an edge which connects vertex  and  directly.2 k -- Find the answer for the query: What's the minimum and maximum possible number of connected components after adding  new edges to the graph. Note that after adding the  edges, the graph must still be a simple graph, and the query does NOT modify the graph.

Please help DreamGrid find the answer for each operation of the second type. Recall that a simple graph is a graph with no self loops or multiple edges.

Input

There are multiple test cases. The first line of the input is an integer , indicating the number of test cases. For each test case:

The first line contains two integers  and  (, ), indicating the number of vertices and the number of operations.

For the following  lines, the -th line first contains an integer  (), indicating the type of the -th operation.

If , two integers  and  follow (, ), indicating an operation of the first type. It's guaranteed that before this operation, there does not exist an edge which connects vertex  and  directly.If , one integer  follows (), indicating an operation of the second type. It's guaranteed that after adding  edges to the graph, the graph is still possible to be a simple graph.

It's guaranteed that the sum of  in all test cases will not exceed , and the sum of  in all test cases will not exceed .

Output

For each operation of the second type output one line containing two integers separated by a space, indicating the minimum and maximum possible number of connected components in this query.

Sample Input

15 51 1 22 11 1 32 12 3

Sample Output

3 32 31 2

解题报告：

以连通块中元素个数为权值，建立线段树，维护三个变量，分别是cnt（这样的连通块的数量），sum（连通块的总的点数），pfh（各连通块之间点数的平方和）（注意不是和的平方）

cnt代表连通块数量，tot_ret代表当前状态下的图，在不增长连通块个数的前提下，可以加的边数。

所以对于最小值很显然。

对于最大值，首先减去块内连的边，然后去线段树查询剩下的边怎么加，首先填连通块元素大小大的，这样也就是类似查询第k大，查到叶子结点，再判断 块中元素为tree[cur].l的 块 我需要多少个 返回回去，就行了。

AC代码：

#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。