[CCO 2024] Telephone Plans 題解

知識點

啟發式合并，啟發式分裂，BFS，LCT。

分析

首先有“所有邊連接起來會得到森林”和“所有邊只會出現一段連續的時間”兩個重要條件。

然后對于連邊和刪邊就有如下算法：

• 連邊：啟發式合并，將較小的連通塊接到較大的上面。
• 刪邊：啟發式分裂，用 BFS 找出大小較小的那邊，注意 BFS 時記錄的節點是原圖的邊，否則會導致復雜度錯誤。

兩者的均攤復雜度皆為 \(O(n\log_2{n})\)。

最后考慮查詢。

我們可以考慮記一個目前總共合并過的節點對數 \(sum\)，每次連邊時，將兩個連通塊 \(u,v\) 的大小相乘并加入 \(sum\)，即 \(sum\gets sum +siz_u\times siz_v\)。

除此之外再記一個 \(d_{i}\) 表示第 \(i\) 次操作使節點對數減少的數量，那么在刪邊時，對于分裂出來的兩個連通塊 \(u,v\)，將他們相乘并記下即可 \(d_i\gets siz_u\times siz_v\)。如果操作不是刪邊，則 \(d_i\gets 0\)。

那么第 \(q\) 次查詢 \(t\) 的答案就是 \(sum-\sum_{i=1}^{q-t}d_i\)，對 \(d\) 做前綴和即可解決。

代碼

已略去快讀快寫。

bool vis[N];
int ALWAYS_ONLINE,n,Q,top;
int idx[N],siz[N],st[N];
ll ans(0),sum(0);
ll del[Qr];
gp_hash_table<int,null_type> g[N];

void dfs(int u,int fa,int new_idx) {
	idx[u]=new_idx;
	for(auto &v:g[u])if(v!=fa)dfs(v,u,new_idx);
}

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	I(ALWAYS_ONLINE,n,Q);
	FOR(i,1,n)idx[i]=i,siz[i]=1;
	FOR(q,1,Q) {
		int op;
		ll x,y,t;
		I(op),op<3?I(x,y):I(t),del[q]=del[q-1];
		if(ALWAYS_ONLINE)op<3?x^=ans,y^=ans:t^=ans;
		if(op==1) {
			int u(idx[x]),v(idx[y]);
			if(siz[u]>siz[v])swap(u,v),swap(x,y);
			st[++top]=u,sum+=(ll)siz[u]*siz[v],siz[v]+=siz[u],dfs(x,0,v),g[x].insert(y),g[y].insert(x);
		} else if(op==2) {
			int u(idx[x]),v(idx[y]);
			g[x].erase(y),g[y].erase(x);
			stack<int> sx,sy;
			queue< pair<int,Hit> > qx,qy;
			vis[x]=true,sx.push(x);
			if(!g[x].empty())qx.push({x,g[x].begin()});
			vis[y]=true,sy.push(y);
			if(!g[y].empty())qy.push({y,g[y].begin()});
			while(!qx.empty()&&!qy.empty()) {
				auto Update=[&](stack<int> &s,queue< pair<int,Hit> > &q) {
					int u(q.front().first),v(0);
					Hit it(q.front().second);
					q.pop(),v=*it;
					if(!vis[v]) {
						vis[v]=true,s.push(v);
						if(!g[v].empty())q.push({v,g[v].begin()});
					}
					if((++it)!=g[u].end())q.push({u,it});
				};
				Update(sx,qx),Update(sy,qy);
			}
			auto Split=[&](stack<int> &sx,stack<int> &sy) {
				siz[u=st[top--]]=sx.size(),siz[v]-=siz[u],del[q]+=(ll)siz[u]*siz[v];
				while(!sx.empty())idx[sx.top()]=u,vis[sx.top()]=false,sx.pop();
				while(!sy.empty())vis[sy.top()]=false,sy.pop();
			};
			qx.empty()?Split(sx,sy):Split(sy,sx);

		} else O(ans=sum-del[q-t],'\n');
	}
	return 0;
}