专栏文章

题解：P11287 [COTS 2017] 影响 Utjecaj

XXCDRF
P11287题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miq9e09b
此快照首次捕获于
2025/12/04 01:06
3 个月前
此快照最后确认于
2025/12/04 01:06
3 个月前
查看原文

P11287 [COTS 2017] 影响 Utjecaj

原题传送门
更好的阅读体验

解题思路

在做本题之前，我们先来考虑一个简单的问题。
给定一个 nn 个点 mm 条边的无向图，点 ii 的点权为 aia_i。定义一个点的影响力为这个点周围所有点和自己的点权和。
有 qq 次操作：
  • 1\texttt{1} uu xx：令 au←xa_u\gets x；
  • 2\texttt{2} vv：查询点 vv 的影响力。
1≤n,m,q≤2×1051\le n,m,q \le 2\times 10^5。
如果暴力的话，每次修改点权都要改周围所有点的值，最坏条件下可能会被卡到 O(qn)O(qn)。考虑设定一个阈值 BB，度数 >B>B 和 ≤B\le B 的点用两种方法处理。修改时如果这个点的度数 ≤B\le B 则暴力修改点权；如果这个点的度数 >B>B 则打上标记，记录现点权和原点权的差值，修改时间复杂度为 O(B)O(B)。查询时答案为暴力修改后的值加上相邻的度数 >B>B 的点的标记。因为总共有 mm 条边，所以度数 >B>B 的点最多有 2mB\frac{2m}{B} 个，查询时间复杂度为 O(mB)O(\frac{m}{B})。总时间复杂度即为 O(q(B+mB))O(q(B+\frac{m}{B}))。
由基本不等式得 B+mB≥2mB+\frac{m}{B}\ge 2\sqrt m，当且仅当 B=mBB=\frac{m}{B} 即 B=mB=\sqrt m 时等号成立，所以总时间复杂度为 O(qm)O(q\sqrt m)。
再来看本题，可以将所有关键点删去，整个图会分成若干个连通块。如果一个关键点和一个连通块相连，则整个连通块都可达。不妨将每个连通块缩成一个点，则一个关键点的影响力就是周围所有点和自己的点权和。这样我们就将本题转化成了上文提到的题目。时间复杂度为 O(qm)O(q\sqrt m)。

参考代码

CPP
#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 记录

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...