题意

对于一个排列\(a1...an\), \(next_i\)表示排列中i后面第一个比\(ai\)大的位置.现给定一个排列的一部分\(next_i\)数组,试据此构造一个排列.
若\(next_i=n+1\)表示i后面没有比它更大的数,\(next_i=-1\)表示不确定.\(n \leq 5*10^5\)

法1: \(O(nlogn)\)

考虑定义,对于任意一个\(nexti\)不等于-1的位置i,有\(ai>aj(i+1\leq j \leq nexti-1),a_{next_i} > a_i\)成立,显然连边+拓扑排序,用线段树优化连边做到\(O(nlogn)\)即可.

法2: \(O(n)\)

• Step1 考虑没有-1,且\(next\)互不相同怎么做.由于交叉必然无解,所以形成的区间是这样的:

容易发现,如果next互不相同,我们按照\(next\)从大到小排序依次填数,方案必定是合法的,原因在于,一个位置有比另一个位置小的限制,当且仅当被一个\((i,next_i)\)的区间覆盖,排序后就保证了右边的比左边小,所以必然合法.

• Step2 考虑有\(next\)相同怎么做.显然,对于\(next\)相等的位置,越靠前,数越大,对于这些位置按照从小到大排序即可.

• Step3考虑有-1怎么做.相当于在不考虑-1形成的区间中加入许多新区间,使其合法,如图:

容易发现,只要让\(i\)直接指向\(i+1\)就不会产生任何交叉区间.如图:

用一个vector存储某个位置作为\(next\)被哪些点指向,扫一遍,依次填数,就是一种合法方案.