自动搬运

查看原文

来自洛谷，原作者为

	honglan0301 AFO —— 只是我的心一直在问，用什么把你永久留下～ | 2024.07.25 — ？

搬运于2025-08-24 22:48:07，当前版本为作者最后更新于2023-06-10 22:57:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目分析

事实上根号分治是完全没必要的，我这里提供一个仅基于分块的时间 $O(n\sqrt n)$，空间 $O(n)$ 做法。

首先这种问题肯定想分块，朴素的区间加区间求和可以使用散块暴力加，整块懒标记的方法处理。而其实本题也可以用同样的方法：还是先对点的编号分块，之后注意到每次询问只会问到一个连通块，于是我们不完全实时地维护每个连通块的点权和，而是对每个连通块 $i$ 分成 $A_i$（表示由散块加上来的值）与 $B_i$（由整块加上来的值）这两部分维护：

前者可以暴力加。后者我们考虑询问时再具体求，这只需对每个连通块维护 $s_{i,j}$ 表示连通块 $i$ 内点编号在第 $j$ 块的点的个数。那么合并连通块 $u,v$ 时令 $A_{v}\leftarrow A_{u}+A_{v}$ 并重构 $s$ 数组即可做到单次 $O(\sqrt n)$ ；询问时有 $ans=A_u+B_u=A_u+\sum s_{u,i}\times tag_i$，直接扫一遍也可以做到单次 $O(\sqrt n)$。

现在的空间是 $O(n\sqrt n)$ 的，不过其实很好处理，因为你注意到只需维护 $s_{i,j}$ 中非零的部分，而显然至多有 $O(n)$ 个 $s_{i,j}$ 是非零的，于是对每个 $i$ 开动态数组即可让空间变成 $O(n)$。

代码

感觉这种做法的代码就挺简洁好懂，非常不错。以下是核心部分代码。

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ll long long
#define B 475

int n,m,opt,u,v,w,k[200005],L[705],R[705],bh[200005],sz[200005],ns[705];
ll sum[200005],tg[705];
vector <pair<int,int>> sm[200005];
vector <int> num[200005];

signed main()
{
	cin>>n>>m; for(int i=1;i<=n;i++) k[i]=(i-1)/B+1; 
	for(int i=1;i<=k[n];i++) L[i]=(i-1)*B+1,R[i]=min(i*B,n);
	for(int i=1;i<=n;i++) bh[i]=i,sz[i]=1,sm[i].pb(mp(k[i],1)),num[i].pb(i);
	while(m--)
	{
		cin>>opt;
		if(opt==1)
		{
			cin>>u>>v; u=bh[u],v=bh[v]; if(u==v) continue; if(sz[u]>sz[v]) swap(u,v);
			for(auto i:num[u]) bh[i]=v,num[v].pb(i); num[u].clear(); num[u].shrink_to_fit();
			for(auto i:sm[u]) ns[i.fi]+=i.se; for(auto i:sm[v]) ns[i.fi]+=i.se; 
			sm[u].clear(); sm[v].clear(); sm[u].shrink_to_fit(); sm[v].shrink_to_fit();
			for(int i=1;i<=k[n];i++) if(ns[i]) sm[v].pb(mp(i,ns[i])),ns[i]=0; sum[v]+=sum[u]; sz[v]+=sz[u];
		}
		else if(opt==2)
		{
			cin>>u>>v>>w; int uu=k[u],vv=k[v];
			if(uu==vv) {for(int i=u;i<=v;i++) sum[bh[i]]+=w;}
			else
			{
				for(int i=u;i<=R[uu];i++) sum[bh[i]]+=w; for(int i=L[vv];i<=v;i++) sum[bh[i]]+=w;
				for(int i=uu+1;i<=vv-1;i++) tg[i]+=w;
			}
		}
		else {cin>>u; u=bh[u]; ll ans=sum[u]; for(auto i:sm[u]) ans+=(ll)i.se*tg[i.fi]; cout<<ans<<endl;}
	}
}