首页 > 试题广场 >

链式边权

[编程题]链式边权

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

第i个点有点权a_i，定义第i条边的权重为w_i：有多少点对x，y满足在第i条边的左侧（x≤i），y在第i条边的右侧（y>i），且x和y的点权不同。

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

第一行输入一个数n。(2≤n≤100000)
第二行输入n个数，a₁,a₂,…,a_n(1≤a_i≤10⁹)

输出n-1个数，依次为每条边的权重，不要在行末输出多余的空格。

示例1

输入

3
1 2 1

1 1

算法知识视频讲解

暂无题解

C++工程师数组分治度小满 2019 查找数学 Java工程师

来自：度小满2019秋招研发岗试卷

上传者：小小

难度：

5条回答 15收藏 6594浏览

查看代码

扫一扫，把题目装进口袋