首页 > 试题广场 >

链式边权

[编程题]链式边权
  • 热度指数:919 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

n个点连成一条链,从左往右依次从1n编号。相邻点之间有边相连,一共有n-1条边。所有的边从1n-1编号,第i条边连接了点ii+1

i个点有点权ai,定义第i条边的权重为wi:有多少点对xy满足在第i条边的左侧(x≤i),y在第i条边的右侧(y>i),且xy的点权不同。

给出每个点的点权,请求出所有边的边权。


输入描述:

第一行输入一个数n。(2≤n≤100000)

第二行输入n个数,a1,a2,…,an (1≤ai≤109)



输出描述:
输出n-1个数,依次为每条边的权重,不要在行末输出多余的空格。
示例1

输入

3
1 2 1

输出

1 1
头像 bandiaoz
发表于 2024-12-27 01:57:24
解题思路 这道题的关键点在于: 个点形成一条链,边的编号从 到 对于第 条边,其权值 定义为:在第 条边左侧 且点权为 的点数,与在第 条边右侧 且点权为 的点数的乘积之和 需要计算每条边的权值 解题思路: 使用两个哈希表分别记录左侧和右侧的点权计数 初始时所有点都在右侧 展开全文