#P7225. [2023省队模拟]单峰序列

    ID: 7059 传统题 1000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-极端元素优先处理贡献法差分转化树状数组倍增求第 k 小差分树状数组离线查询

[2023省队模拟]单峰序列

题目描述

如果一个长度为 nn 的序列存在一个位置 kk(1≤k≤n1\le k\le n),使得 ai<ai+1a_i<a_{i+1} 对所有 1≤i<k1\le i<k 成立,并且 ai>ai+1a_i>a_{i+1} 对所有 k≤i<nk\le i<n 成立,则称这个序列为单峰序列。

一个序列的权值是将它变成单峰序列所需的最少相邻交换次数。一次操作交换两个相邻的元素。

给定一个长度为 nn 的排列 a1,a2,…,ana_1,a_2,\ldots,a_n。根据测试点类型,求整个排列或排列每个前缀的权值。

输入格式

第一行两个整数 n,tn,t,分别表示排列长度和测试点类型。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示 11 到 nn 的一个排列。

原题文件名为 seq.in 和 seq.out。

输出格式

若 t=0t=0,输出一行一个非负整数,表示整个排列的权值。

若 t=1t=1,输出 nn 行。第 ii 行是前缀 a1,a2,…,aia_1,a_2,\ldots,a_i 的权值。

样例

10 1
2 10 5 1 3 7 4 9 6 8
0
0
0
0
1
4
6
8
9
11

数据范围

1≤n≤5×1051\le n\le 5\times10^5,t∈{0,1}t\in\{0,1\}。

测试点 nn 的上限 tt
1–2 2020 11
3–4 100100
5–6 500500
7–8 10001000
9–10 50005000 00
11–12 11
13–15 5×1055\times10^5 00
16–20 2×1052\times10^5 11
21–25 5×1055\times10^5