解题思路
相邻股道闸口 j 的过闸代价 cj:当 bj<bj+1 时为 1,否则为 0。
标准冒泡从左到右扫描。原优先级序列中第 i 节车厢 ai 会与左边所有比它大的车厢交换,设这样的个数为 cnti。它每次向左最多移动一格,因此会依次经过边 i−1,i−2,…,i−cnti,贡献为这些边上 c 值之和。
预处理前缀和 prei=c1+⋯+ci,则第 i 个元素贡献为 prei−prei−cnti(0-index 下即 pre[i]−pre[i−cnt])。
问题转化为:对每个 ai 求左边有多少个数严格大于它。先离散化,再用树状数组维护已出现元素个数。对当前 ai: