自动搬运

查看原文

来自洛谷，原作者为

	缪凌锴_Mathew 希↑望→计↓划↑可→以↑成↓功↓ | 离错真机

搬运于2025-08-24 23:08:03，当前版本为作者最后更新于2025-01-07 16:26:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

非 LCT 做法。

解法

有一个非常重要的隐藏信息：“每条电话线只能在一段时间内使用”，这意味着每条边只会被加入一次。

对于一组点对 $(x,y)$，其连通的时间必为一个连续段 $[l_{x,y},r_{x,y}]$。

查询 $t$，当前时间为 $s$，即计算 $\displaystyle\sum_{(x,y)}\Big[[l_{x,y},r_{x,y}]\cap(s-t,s]\ne\varnothing\Big]$（外层大中括号为艾弗森括号）

我们分成两部分：

• $l_{x,y}\le s$，也就是在此之前连通过的点对 $(x,y)$ 的数量 $cur$。

• $r_{x,y}> s-t$。

  记 $del_i$ 为满足时刻 $i-1$ 连通且时刻 $i$ 不连通的点对 $(x,y)$ 数量。（显然 $i$ 为删边操作才有值）

询问答案即为 $cur-\sum\limits_{i=1}^{s-t}del_i$。

对于第一部分，考虑启发式合并。

连边 $(u,v)$ 时，对 $cur$ 贡献 $siz_u\times siz_v$，其中 $siz_x$ 表示当前 $x$ 所处连通块大小。

对于第二部分，考虑启发式分裂。

删边 $(u,v)$ 时，同时 bfs $u,v$ 所处连通块，bfs 完一个连通块所有点就退出，$del=siz_u\times siz_v$。

复杂度分析

注意到两个操作复杂度都为 $O(\min\{siz_u,siz_v\})$。

• 连边操作：若没有删边，总复杂度应为 $O(n\log n)$（启发式合并），有删边只会使复杂度更小。

• 删边操作：若没有连边，总复杂度应为 $O(n\log n)$（启发式分裂），有连边只会使复杂度更小。

故总复杂度 $O(n\log n+q)$。

实现细节

• 强制在线，不能预先知道树的形态，故用 set 作邻接表存树。（我用了 unordered_set）

• 删边的 bfs 特别注意：

  用两个队列，每次扩展一个点所有出边是错误的，这样复杂度并不是 $O(\min\{siz_u,siz_v\})$。

  需要一条一条边扩展，但是这个 set 邻接表非常麻烦，要把边对应的迭代器也扔进队列。

• 扩展时注意父子关系，不要父亲扩展儿子、儿子扩展回父亲。

• 答案为 long long 级别，强制在线，输入也要开 long long。

Code

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<numeric>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=5e5+10;
const int MAXM=1.5e6+10;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
int n,m,typ;
long long ans=0,cur=0;
long long del[MAXM];
int t;//当前时间戳
int tim[MAXN];//这个数组充当 bool vis[MAXN] 的作用，记录上次访问时间戳，这样就不用清空
#include<unordered_set>
struct splitmix64{
	inline int operator ()(int x)const{
		x^=x<<13;
		x^=x>>11;
		x^=x<<7;
		return x;
	}
};
unordered_set <int,splitmix64> tr[MAXN];
inline void add_edge(int x,int y){
	tr[x].insert(y);
	tr[y].insert(x);
}
inline void del_edge(int x,int y){
	tr[x].erase(y);
	tr[y].erase(x);
}
int siz[MAXN],col[MAXN];
basic_string <int> wst;//连通块编号(col)的垃圾回收
void flood_fill(int x,int rt){
	tim[x]=t;
	siz[rt]++;
	col[x]=rt;
	for(int to:tr[x])
	{
		if(tim[to]==t){
			continue;
		}
		flood_fill(to,rt);
	}
}
inline long long link(int x,int y){
	add_edge(x,y);
	if(siz[col[x]]<siz[col[y]]){
		swap(x,y);
	}
	long long res=1ll*siz[col[x]]*siz[col[y]];
	siz[col[y]]=0;
	wst.push_back(col[y]);
	tim[x]=t;
	flood_fill(y,col[x]);
	return res;
}
#define node tuple<int,unordered_set <int,splitmix64>::iterator>
inline long long cut(int x,int y){
	del_edge(x,y);
	queue <node> p,q;
	if(!tr[x].empty()){
		p.push(node(x,tr[x].begin()));
	}
	if(!tr[y].empty()){
		q.push(node(y,tr[y].begin()));
	}
	while(!p.empty()&&!q.empty())
	{
		#define work(Q){\
			auto [x,it]=Q.front();\
			tim[x]=-t;/*这里的-t是弹出队列的标记*/\
			Q.pop();\
			if(tr[*it].size()>1){\
				auto to=tr[*it].begin();\
				if(*to==x){\
					to++;\
				}\
				Q.push(node(*it,to));\
			}\
			it++;\
			if(it!=tr[x].end()&&tim[*it]==-t){/*若*it已弹出队列，则*it为x的父亲*/\
				it++;\
			}\
			if(it!=tr[x].end()){\
				Q.push(node(x,it));\
			}\
		}
		work(p);
		work(q);
	}
	if(p.empty()){
		swap(x,y);
	}
	int rt=wst.back();
	wst.pop_back();
	flood_fill(y,rt);
	siz[col[x]]-=siz[col[y]];
	return 1ll*siz[col[x]]*siz[col[y]];
}
inline void solve(){
	scanf("%d",&typ);
	scanf("%d%d",&n,&m);
	iota(col+1,col+1+n,1);
	fill(siz+1,siz+1+n,1);
	for(t=1;t<=m;t++)
	{
		del[t]=del[t-1];
		int opt;
		scanf("%d",&opt);
		if(opt^3){
			long long x,y;
			scanf("%lld%lld",&x,&y);
			if(typ){
				x^=ans;
				y^=ans;
			}
			if(opt==1){
				cur+=link(x,y);
			}
			else{
				del[t]+=cut(x,y);
			}
		}
		else{
			long long x;
			scanf("%lld",&x);
			if(typ){
				x^=ans;
			}
			ans=cur-del[t-x];
			printf("%lld\n",ans);
		}
	}
}
signed main(){
	#ifdef LOCAL
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	atexit([](){fprintf(stderr,"%.3lfs\n",(double)clock()/CLOCKS_PER_SEC);});
	#endif
	solve();
	return 0;
}