Description:


DZY开始有 n 个点,现在他对这 n 点进行了 m 次操作,对于第 i 个操作(从 1 开始编号)有可能的三种情况:
Add a b: 表示在 a 与 b 之间连了一条长度为 i 的边(注意,i是操作编号)。保证 1≤a,b≤n。
Delete k: 表示删除了当前图中边权最大的k条边。保证 k 一定不会比当前图中边的条数多。
Return: 表示撤销第 i−1 次操作。保证第 1 次操作不是 Return 且第 i−1 次不是 Return 操作。
请你在每次操作后告诉DZY当前图的最小生成树边权和。如果最小生成树不存在则输出 0。

Input:


第一行两个正整数 n,m。表示有 n 个点 m 个操作。 接下来 m 行每行描述一个操作。

Output:


对于每一个操作输出一行一个整数表示当前最小生成树边权和。

Sample Input:


Sample Output:


题解:


非常好的一道题,我几乎把每一个部分分都做了一下....

30分做法:

这个十分简单,注意到边权为i,所以一定递增,就可以免去排序的过程。
直接开数组维护边,每次用Kruskal求最小生成树。
时间复杂度: \(O(m^2 \time \alpha (n) )\)
代码如下:

50分做法:

考虑只有Add的情况,因为边权是递增的,若存在最小生成树,则不管怎样加边不影响答案。
直接对所有的边使用Kruskal,在最后加入的边之前答案全部为0,后面的全部为ans。
时间复杂度 \(O(m\alpha (n))\)
然后加上之前30分的程序,可以拿到50分。
注意开long long。
代码如下:

70分做法:

考虑没有Return的数据。
对于并查集不进行路径压缩,按照子树大小合并。
Add操作时把边放入一个栈中,Delete操作时,弹出栈顶k个元素,若其中有边在最小生成树上,在并查集上删除对应的边。
因为最多存在m条边,所以时间复杂度 \(O(m log_2 n)\)
配合30分程序,可以拿70分。
代码如下:

100分做法:

考虑离线处理。
如果一个Return操作前是Add操作,则该Return操作等同于Delete 1。
如果一个Return操作前是Delete操作,则在该Delete操作时,不执行删除,直接计算k是否大于栈顶不在最小生成树上的边的条数,如果大于,答案为0,否则答案为ans。
巧妙地处理了Return操作。
该算法复杂度为 \(O(m log_2 n)\)
代码如下:

这个题目还可以用可持久化并查集来做,但时间复杂度不如上面的方法,所以没有写代码,欢迎各位大神在评论中贴出。