题意：有一个序列，但你不知道它长什么样，你只知道现在有些位置后面第一个比它大的数。要你找出一个可行的原序列。

思路：首先这一看就是道图论题。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

我们考虑根据数的大小情况建一个有向图，然后它的拓扑排序就是答案。

首先我们假设\(i\)的后面第一个比\(a_i\)大的是\(nxt_i\)。然后我们的\(i\)肯定要连到\(nxt_i\)，\(i+1\)到\(nxt_i-1\)都要连到\(i\)。

那么我们需要一个区间连到一个点，直接线段树优化建图。

但是我觉得区间连到点没有点连到区间好写，所以我把每条边反向了。

我们线段树上的每个点连到左右儿子，然后从\(i\)连到\([i+1,nxt_i-1]\)的时候就把\(i\)连到\([i+1,nxt_i-1]\)包含的\(O(\log n)\)个完整的区间就好了。

然后我们现在就有\(2n\)个节点。拓扑排序也要不了太多时间。只是边数\(O(n\log n)\)稍多了点。

把命交给CF评测机

但是这题是多测，我写线段树的习惯是直接开N=1<<19，然后初始化是\(O(N)\)的，有\(T=100000\)组数据。。。

Time limit exceeded on pretest 3。。。

然后我在最后\(20min\)才写完这个方法，一\(tle\)就慌掉了，于是：

Wrong answer on pretest 1。。。

\(What\)？？？

The contest is ended. Reload the page for more information.

S**T。

考完立马想到了问题（因为心情平静了一点），后悔死了。

不过这也有第一次写线段树优化建图这种东西的原因吧。不过占比比较小。

主要是想到比较晚，心态崩掉了。

还有就是坑了比较久的B。

然后几个综合起来就挂掉了啊。

早知道就先用线段树优化建图写一遍R1D1T2 字符串问题了。

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄