P13875 [蓝桥杯 2024 省研究生组] 植物生命力 - 题解

思路：

看起来不太可做，但我们可以注意到题目中有这样一句话：对于所有的测试用例，

1 \le a_i \le n

，

a_1, a_2, \ldots, a_n

互不相同。这说明所有的节点权值组成了一个

1

到

n

的排列，这是一个良好的性质。

对于这道题，一个显然的思路就是：对于所有的

i

查询子树内小于

a_i

的权值个数，再减去子树内被

a_i

整除的权值个数，前者需要使用可持久化线段树才能解决，而后者直接计算也十分困难，所以我们考虑另一个思路：计算每一个节点对答案产生的贡献，由此产生了一个显然的算法：当遍历到该节点时将这个节点权值插入线段树，查询线段树内插入的权值有多少个比该权值大，再减去线段树内是该权值整数倍的权值，然后从线段树中删除该节点。线段树的部分容易解决，而减去整数倍的部分却几乎不可做，似乎陷入了僵局。但此时回到开头提到的性质：节点权值是一个

1

到

n

的排列，那么我们就可以直接对每一个权值枚举它的整数倍是否在线段树中，对于权值

1

，要枚举

\frac{n}{1}

次；对于权值

2

，要枚举

\frac{n}{2}

次，以此类推，对于整棵树，总共要枚举：

\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+\cdots+\frac{n}{n}

这么多次，即

n\ln{n}

次，可以通过此题。

一些显然的优化：可以用树状数组代替线段树，以减小常数；把权值插入树状数组的同时打标记，这样在枚举整数倍的时候可以做到

O(1)

查询而无需在树状数组上查询。

代码：

CPP

vector<int> mp[100005];
int w[100005];
bool vis[100005];
int n,rt;
long long ans;
int c[100005];
void add(int x,int v)
{
	for(;x<=n;x+=lowbit(x))	c[x]+=v;
}
int qry(int x)
{
	int res=0;
	for(;x;x-=lowbit(x))	res+=c[x];
	return res;
}
void dfs(int u,int f)
{
	vis[w[u]]=1;
	add(w[u],1);
	for(int v:mp[u])
	{
		if(v==f)	continue;
		dfs(v,u);
	}
	for(int i=2;i*w[u]<=n;i++)
		ans-=vis[i*w[u]];
	ans+=qry(n)-qry(w[u]);
	vis[w[u]]=0;
	add(w[u],-1);
}
char QQ,coin;
decltype(QQ+coin) main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>rt;
	for(int i=1;i<=n;i++)
		cin>>w[i];
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		mp[u].push_back(v);
		mp[v].push_back(u);
	}
	dfs(rt,0);
	cout<<ans<<"\n";
	return ~(-1);
}

题解：P13875 [蓝桥杯 2024 省研究生组] 植物生命力

文章操作

P13875 [蓝桥杯 2024 省研究生组] 植物生命力 - 题解

思路：

代码：

相关推荐

评论

题解：P13875 [蓝桥杯 2024 省研究生组] 植物生命力