链接：https://www.luogu.com.cn/problem/P6198
题目描述：给定一个长为\(n\)数列\(S\)，求一个字典序最小的排列，使得将这个排列依次放入单调栈中序列中元素的个数与\(S\)一一对应。
题解：介绍一个拓扑排序的做法。
假如我们先不考虑\(S_{i}!=1\)的情况，先考虑一下假如我们将一个排列放入一个单调栈会有什么性质，我们发现有：
\(1\).若\(S_{i-1}<S_{i}\)，那么肯定有\(S_{i}=S_{i-1}+1\)，因为最多只能增加一个数，那么我们就可以知道\(p_{i-1}<p_{i}\)。
\(2\).若\(S_{i-1}>=S_{i}\)，则在这个单调栈中第\(S_{i}\)个元素以及后面的元素全都会被\(pop\)掉，那么我们就可以得到两个关系式：\(p_{d_{S_{i}}}>p_{i}\),\(p_{d_{S_{i}}-1}<p_{i}\)。
若我们记\(t_{i}\)表示我们目前可以得到的最大的小于\(p_{i}\)的\(p\)序列的元素对应的下标，那么我们就可以把原问题转化为偏序问题。
我们可以发现：
\(1\).当\(i\)始终在单调栈时，根据上面的分析，则有\(t_{i}=pre_{i}\)(\(pre_{i}\)表示\(i\)在单调栈的前驱)
\(2\).当\(i\)被\(j\)弹掉时，根据上面的分析\(t_{i}=pre_{i}\)或\(j\)，那么由于我们是要取最大的，则
假如\(i\)是被\(j\)弹掉中最小的，则\(t_{i}=j\)
假如\(i\)不是被\(j\)弹掉中最小的，则\(t_{i}=pre_{i}\)，因为\(pre_{i}\)被\(j\)弹掉，则\(pre_{i}\)是比\(j\)大的。
则我们给每一个点连一条\((t_{i},i)\)的边，则原问题转化为，按照拓扑排序遍历一个有向图，令\(dfn_{i}\)是\(i\)号节点是\(dfn_{i}\)个被遍历的，最小化\(dfn_{i}\)的字典序。
我们发现，最小化\(dfn_{i}\)的字典序等同于遍历时尽量使\(1\)靠前，在\(1\)尽量靠前的情况下再使\(2\)尽量靠前......我们发现这个问题就是[\(HNOI2015\)]菜肴制作，所以我们只要求出在反图跑最大的的字典序的反序就可以了。
再考虑可以为\(-1\)的情况，这种情况可以令\(S_{i}=S_{i-1}+1\)，这样可以保证有解，然后你会发现这样有一定是最优的，具体我不会证。
复杂度\(O(nlogn)\)
#include<iostream>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
struct node
{
int v,nxt;
};
node edge[2000001];
int head[1000001],d[1000001],top,len,length,in[1000001],S[1000001],n,p[1000001],rk[1000001];
int que[1000001];
void add(int x,int y)
{
edge[++len].v=y;
edge[len].nxt=head[x];
head[x]=len;
return;
}
priority_queue<int>q;
void top_sort()
{
int tp;
for (int i=1;i<=n;++i)
if (in[i]==0)
q.push(i);
while (!q.empty())
{
tp=q.top();
d[++length]=tp;
q.pop();
for (int i=head[tp];i>0;i=edge[i].nxt)
{
in[edge[i].v]--;
if (in[edge[i].v]==0)
q.push(edge[i].v);
}
}
return;
}
signed main()
{
cin>>n;
for (int i=1;i<=n;++i)
cin>>S[i];
for (int i=1;i<=n;++i)
if (S[i]==-1)
S[i]=S[i-1]+1;
for (int i=1;i<=n;++i)
{
if (S[i-1]<S[i])
{
p[i]=i-1;
que[++top]=i;
}
else
{
p[i]=que[S[i]-1];
if (S[i]<=top)
p[que[S[i]]]=i;
top=S[i]-1;
que[++top]=i;
}
}
for (int i=1;i<=n;++i)
if (p[i]!=0)
{
add(i,p[i]);
in[p[i]]++;
}
top_sort();
for (int i=1;i<=n/2;++i)
swap(d[i],d[n-i+1]);
for (int i=1;i<=n;++i)
rk[d[i]]=i;
for (int i=1;i<=n;++i)
cout<<rk[i]<<' ';
cout<<endl;
return 0;
}