主题

主题

 
   

3514: Codechef MARCH14 GERALD07加强版

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=3514

Description

N个点M条边的无向图,询问保留图中编号在[l,r]的边的时候图中的联通块个数。

Input

第一行四个整数N、M、K、type,代表点数、边数、询问数以及询问是否加密。

接下来M行,代表图中的每条边。

接下来K行,每行两个整数L、R代表一组询问。对于type=0的测试点,读入的L和R即为询问的L、R;对于type=1的测试点,每组询问的L、R应为L xor lastans和R xor lastans。

Output

K行每行一个整数代表该组询问的联通块个数。

Sample Input

3 5 4 0

1 3

1 2

2 1

3 2

2 2

2 3

1 5

5 5

1 2

Sample Output

2

1

3

1

HINT

对于100%的数据,1≤N、M、K≤200,000。


个人解法:

不会做啊看题解。Po姐与Hzwer都同时引用一段话,感觉很厉害啊。

不过后来想了一下也不是那么地不可想。

记得在做数颜色一题的时候,关于树套树的做法,是记录一个数字出现的last。之后对last来建主席树。然后查找[l..r]区间内的last属于[l..r]的数字的个数sum。

用总的数字的个数len减去last在[l..r]里面的数字的个数sum,就是答案。

原理在于处理掉了对答案无贡献意义的数字。

此题,我们同样记一个数组ntr。如果当前边i加入的时候,形成了 环,就把当前环的最早加入的边删去,并记为当前边的ntr的值。

我们维护的是一棵最大生成树。

如果没有形成环,就令ntr=0。

我们考虑,对于区间[l..r]的边v,如果ntr[v]也是属于[l..r]的,那么这条边是没有意义的。因为加入或者不加入都不会增加或者减少连通块的个数。

反之,如果ntr[v]不属于[l..r](而ntr[v]不为0),那么这条边的加入必然会使得两个连通块相连。假设ntr[v]=y。因为在v之前,没有边在y之后把v所连接的两个点再次连接起来(否则ntr[v]就不会是y),所以v就是第一个在[l..r]中,第一个把它所连接的点连接起来的。

因此,我们统计[l..r]中,有多少边的ntr属于[l..r]即可。假设统计出y条边的ntr是在[l..r]范围的,令x=边的总数量(即r-l+1)-y,得到有意义的边的数量。最终答案ans=n-y。

时间复杂度为O(nlogn)。


代码如下:

https://code.csdn.net/snippets/2226488

 
 
评论
 
 
热度(1)