#P4051. [Cerc2013] History course

    ID: 3253 传统题 3000ms 128MiB 尝试: 4 已通过: 2 难度: 9 上传者: 标签>CF2800省选/NOI-二分答案排序贪心交换论证懒标记线段树线段树上二分

[Cerc2013] History course

题目描述

你被给定一系列关于重要的历史事件的演讲,每件事对应一场演讲。

它们不按顺序排列,每件历史事件持续一个时间段 [ai,bi][a_i,b_i]。

如果两件事的时间有共同区间,我们说它们是有关联的,把关于有关联的历史事件的演讲排的彼此靠近能使课程更便于理解。

此外,不相关的演讲必须按历史事件的发生时间排序(如果 A 在 B 之前发生,且 AB 不相关,那么关于 A 的演讲必须在 B 之前进行)。

找出最小的整数 kk (k≥0k \ge 0) 和一个演讲的顺序,使得排序后任意两场相关的演讲之间的间隔不超过 kk(第 ii 场演讲和第 jj 场演讲之间的间隔是 ∣i−j∣|i-j|)。

输入格式

第一行包括数据组数 TT。

每组数据的第一行是一个数 nn,接下来 nn 行每行包括两个整数 [ai,bi][a_i,b_i],区间两两不相同。

输出格式

每组数据答案的第一行是一个最小值 kk,接下来 nn 行按顺序列举排列后的演讲的历史区间(与输入中的格式一样),使得任意两个相关的演讲间隔不超过 kk。

切记将不相关的演讲按时间顺序排列!

1 
3 
1 6 
2 3 
4 5
1 
2 3 
1 6 
4 5

样例说明

共有三个历史事件,其中 1,21,2,1,31,3 是相关的,2,32,3 不相关,且 22 在 33 之前发生,所以 22 应该排在 33 的前面。

对于相关的历史事件,11 与 22 在排列后的位置是 22 和 11,间隔为 11,11 与 33 在排列后的位置为 22 与 33,间隔为 11,所以此时 kk 最小为 11,该排法最优。

数据规模与约定

对于 100%100\% 的数据,1≤n≤5×1041 \le n \le 5 \times 10^4,−109≤ai≤bi≤109-10^9 \le a_i \le b_i \le 10^9。