找出排列是否可能

Question

给定一个从1到N的自然整数的排列。最初，排列是1,2,3，…我们也有M对整数，其中第i对是(Li,Ri)。在一个回合中，我们可以选择这些对中的任何一对(假设索引为j)，并任意洗牌从Lj到Rj的位置上的排列元素，包括(位置是基于1的)。我们没有限制的次数，你可以选择任何一对超过一次。

目标是得到给定的排列p。如果可能，输出" possible"，否则输出"Impossible"。

示例:设N=7, M=4，数组为[3 1 2 4 5 7 6]，查询为:

1 2
4 4
6 7
2 3

Answer 1

将每对作为一个区间，计算区间的并集作为一个不重叠区间的列表，然后对每一个i，检验该排列的i位置的值是否为i，或者是否与i在同一个不重叠区间内。

这是有效的，因为如果我们有a <= b <= c <= d与(a, c)和(b, d)对，那么通过重复调用(a, c)和(b, d)，我们可以得到(a, d)可以得到的任何排列。相反，(a, d)支持(a, c)和(b, d)所能得到的任何排列。一旦配对列表没有重叠，很明显，当且仅当i和j在相同的区间内时，我们可以将元素i移动到j != i的位置。