题目描述

Hercier 作为一位喜爱 Hatsune Miku 的 OIer,痛下决心,将 Vocaloid 买回了家。打开之后,你发现界面是一个长为 n 的序列,代表音调,并形成了全排列。你看不懂日语,经过多次尝试,你只会用一个按钮:将一段区间按升序排序。不理解音乐的 Hercier 决定写一个脚本,进行 m 次操作,每次对一段区间进行操作。可惜 Hercier 不会写脚本,他找到了在机房里的你,请你模拟出最后的结果。

输入格式

第一行两个整数 $n, m, L, R$,$n\leq 1500, m\leq 1 \times 10^6$。

接下来一行 $n$ 个数,表示每个位置的音调 $a_i$。然后 $m$ 行,每行两个数 $l_i, r_i$,表示操作的区间为 $[l_i, r_i]$。

输出格式

一行 $R-L+1$ 个数,表示最终序列的 $a_L, a_{L+1}, \cdots, a_R$。

思路

这道题前 20% 数据可以直接暴力模拟;

另有 50% 数据 $L=R$,可以二分答案,线段树对 01序列排序,直接求出这个点的数值;

对于 100% 的数据:

我们发现对于一个全排列,排序的一个优秀的方法是交换相邻的逆序对。因为逆序对个数的上限是 $\Theta(n^2)$,我们对于每次操作在区间内暴力交换相邻的逆序对即可,每一次交换最多产生两个新的逆序对。用 $std::set$ 维护所有相邻逆序对的位置,每次操作不断在区间内二分查找逆序对,交换对应的 $a$,然后插入新增的逆序对即可。

时间复杂度 $\Theta((n^2+m)\log n)$。

代码

(感觉不需要放代码啊 233)
(这道题作为本场模拟赛的 T3,代码量小的惊人,倒是前 $70%$ 更加难打 233)

前 70%

正解

  1. 【BZOJ 4534】基础排序练习题 / 题解 – XG Zepto's
    Nov 03, 2018

    […] 【Fortuna OJ 5947】初音未来 / 题解 […]

    Reply