主题

主题

 
   

3562: [SHOI2014]神奇化合物

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

Description

科学家最近发现了一种高分子有机化合物 SHTSC。这种物质的分子由单个或多个原子组成,原子之间通过化学键相互连接。SHTSC 十分不稳定,其原子之间的化学键经常会伴随着炫酷的声音特效和光影效果发生断裂或者重新连接。

然而,令科学家们大为惊异的是,SHTSC 在变化过程中始终保持着一种特殊的性质:即不存在这样的原子序列 a1,a2,...,an(n>3)满足 a1 与 a2、a2 与a3、......、an-1 与 an 以及 an 与 a1 都通过化学键相连,但它们之间却没有其他化学键相连的情况。

现在科学家将 SHTSC 的原子由 1 到 n 标号,并告诉你SHTSC 的初始形态以及原子之间的化学键变化情况,他们想知道在实验过程中的某些时刻 SHTSC 分裂成了多少个分子?

Input

第一行两个整数:n, m。表示 SHTSC 的总原子个数以及初始的化学键数。

从第二行开始的 m 行,每行两个整数 a, b (1≤a,b≤n)。表示编号为 a, b 的两

个原子在初始状态中有化学键相连。数据保证每对 a, b 只出现一次。

第 m+2 行有一个整数:q。表示实验的总操作数。

之后 q 行中的每一行为以下三种操作当中的一种:

1、A i j 表示 i 号原子与 j 号原子之间形成了一条新的化学键;

2、D i j 表示 i 号原子与 j 号原子之间原有的化学键断裂了;

3、Q 询问当前 SHTSC 分裂成了多少个不同的分子。

数据保证所有的实验操作都是合法的。

Output

对于每个 Q 操作,输出一行一个整数,为相应时刻的分子个数。

Sample Input

7 10

1 2

2 3

3 4

4 1

1 3

2 4

5 6

6 7

7 5

2 5

10

D 2 5

D 5 6

D 5 7

A 2 5

A 5 6

Sample Output

1

2

3

2

1

HINT

对于 100%的数据, n≤5000,m≤200000,q≤10000。


个人解法:

一看到加边+删边,就想到LCT。结果不是一棵树……脑补了很久。

结果没有想到。因为要对拍,所以想了一个暴力。我们就按照它所说的,加边就O(1)加边,删边就O(m)删边,查询就O(n+m)查询,然后复杂度变为O(q(n+m))。

然后敲完暴力。又脑补了好久,始终想不出给出的这个性质应该怎么用,倒是突然从q与n的极小范围想到了一个暴力的优化。

我们尝试没有被删掉的边自然是可以始终连接两个点不会分裂的。那我们先把这些点连起来。这样做似乎没有把点缩小很多,但是只剩下了O(q)的边是有影响的。于是我们的查询修改啥的就变为了O(q)与O(n+q)。

然后总的复杂度就变为了O(q(n+q))=3e8。问了一下某PbTfLcx,虚了,怕BZOJ过不去,于是就继续脑补。

然后想了一个晚上。第二天起来看题解……

结果几个博客就是这么瞎搞的!


代码如下:

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


由于虚,就想卡一下常啥的。把点数边数什么的都存了起来减少枚举量。

成功跻身于BZOJRank3。



在训练了一段LCT之后,某点bie看到本文,想到了一个比较科学的想法:

如同BZOJ_4025一样的思路。我们用一棵LCT维护消失时间为关键字的最大生成树。

之后link与cut的时候计算一下贡献即可。

时间复杂度为O((m+q)log(n+m+q))

懒的卡常了。就没有动笔写了。

但是此方法说明了此题的n与m是可以达到1e5级别的。也是一个重要的突破。

若有大佬hack掉了此解法,欢迎来裱。

 
 
评论