自动搬运

查看原文

来自洛谷，原作者为

	XCDRF_ May you,the beauty of this world,always shine.

搬运于2025-08-24 23:06:06，当前版本为作者最后更新于2025-02-14 15:07:36，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P11287 [COTS 2017] 影响 Utjecaj

原题传送门

更好的阅读体验

解题思路

在做本题之前，我们先来考虑一个简单的问题。

给定一个 $n$ 个点 $m$ 条边的无向图，点 $i$ 的点权为 $a_i$。定义一个点的影响力为这个点周围所有点和自己的点权和。

有 $q$ 次操作：

• $\texttt{1}$ $u$ $x$：令 $a_u\gets x$；
• $\texttt{2}$ $v$：查询点 $v$ 的影响力。

$1\le n,m,q \le 2\times 10^5$。

如果暴力的话，每次修改点权都要改周围所有点的值，最坏条件下可能会被卡到 $O(qn)$。考虑设定一个阈值 $B$，度数 $>B$ 和 $\le B$ 的点用两种方法处理。修改时如果这个点的度数 $\le B$ 则暴力修改点权；如果这个点的度数 $>B$ 则打上标记，记录现点权和原点权的差值，修改时间复杂度为 $O(B)$。查询时答案为暴力修改后的值加上相邻的度数 $>B$ 的点的标记。因为总共有 $m$ 条边，所以度数 $>B$ 的点最多有 $\frac{2m}{B}$ 个，查询时间复杂度为 $O(\frac{m}{B})$。总时间复杂度即为 $O(q(B+\frac{m}{B}))$。

由基本不等式得 $B+\frac{m}{B}\ge 2\sqrt m$，当且仅当 $B=\frac{m}{B}$ 即 $B=\sqrt m$ 时等号成立，所以总时间复杂度为 $O(q\sqrt m)$。

再来看本题，可以将所有关键点删去，整个图会分成若干个连通块。如果一个关键点和一个连通块相连，则整个连通块都可达。不妨将每个连通块缩成一个点，则一个关键点的影响力就是周围所有点和自己的点权和。这样我们就将本题转化成了上文提到的题目。时间复杂度为 $O(q\sqrt m)$。

参考代码

#include<iostream>
#include<unordered_map> 
#include<cmath>
#define int long long
using namespace std;
const int N=2e5+5;
unordered_map<long long,bool> vis;
int n,m,tot,tot2,tot3,cnt,cnt2,B,q;
int head[N],h[N],b[N],sum[N],a[N],t[N],deg[N],big[N],ans[N];
struct Edge{
	int nxt,to;
}edge[N<<1],e[N<<1];
struct E{
	int fr,to;
}ee[N];
void add(int x,int y){
	edge[++tot]={head[x],y};
	head[x]=tot;
}
void add2(int x,int y){
	e[++tot2]={h[x],y};
	h[x]=tot2;
}
void dfs(int x){
	for(int i=head[x];i;i=edge[i].nxt){
		int xx=edge[i].to;
		if(b[xx]) continue;
		b[xx]=cnt;//存该点属于哪个连通块
		sum[cnt]+=a[xx];
		dfs(xx);
	}
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	cin>>t[i];
    	if(t[i]) b[i]=++cnt;//关键点自己是一个连通块
	}
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	if(t[i]) sum[b[i]]=a[i];//存关键点的点权
	}
    for(int i=1,x,y;i<=m;i++){
    	cin>>x>>y;
    	if((!t[x])&&(!t[y])){
    		add(x,y);//求连通块时用的边
    		add(y,x);
		}
		if(t[x]&&t[y]) continue;
		ee[++tot3]={x,y};//连通块之间的边，关键点和关键点之间没有边
	}
	for(int i=1;i<=n;i++){
		if(t[i]||b[i]) continue;
		b[i]=++cnt;
		sum[b[i]]+=a[i];
		dfs(i);//求出连通块大小和点权和
	}
	for(int i=1;i<=tot3;i++){
		int x=ee[i].fr,y=ee[i].to;
		x=b[x],y=b[y];
		if(x!=y&&!vis[x*2e5+y]){//如果这两个点不属于一个连通块且两个连通块间没有连边就连一条边
			add2(x,y);
			add2(y,x);
			vis[x*2e5+y]=vis[y*2e5+x]=1;
			deg[x]++,deg[y]++;
			cnt2+=2;
		}
	}
	vis.clear();
	B=sqrt(cnt2);//阈值大小
	cnt2=0;
	for(int x=1;x<=cnt;x++){
		if(deg[x]>B) big[++cnt2]=x;//记录大点信息
		for(int i=h[x];i;i=e[i].nxt){
			int xx=e[i].to;
			if(deg[xx]>B) vis[xx*2e5+x]=1;
			if(deg[x]>B) ans[x]+=sum[xx];//大点初始答案
		}
	}
	cin>>q;
	//本代码与思路中描述稍有区别，修改复杂度O(m/B)，查询复杂度O(B)
	while(q--){
		int op,x,y;
		cin>>op;
		if(op==1){
			cin>>x>>y;
			int w=y-a[x];
			sum[b[x]]+=w;//修改连通块点权和
			for(int i=1;i<=cnt2;i++)
				if(vis[big[i]*2e5+b[x]]) ans[big[i]]+=w;//枚举与该点有连边的大点进行修改
			a[x]=y;
		}
		else{
			cin>>x;
			x=b[x];
			if(deg[x]<=B){//小点直接枚举所有相邻连通块
				int anss=sum[x];
				for(int i=h[x];i;i=e[i].nxt){
					int xx=e[i].to;
					anss+=sum[xx];
				}
				cout<<anss<<'\n';
			}
			else cout<<ans[x]+sum[x]<<'\n';//大点答案已预处理，直接输出
		}
	}
	return 0;
}

本题细节较多，写代码时需要仔细。

AC 记录