中文题意
求一个由最多26个、最少k个小写字母构成的，长度为n的字符串，这个字符串要满足的要求是——当其中字母按照p和q两个\(1\)~\(n\)的全排列重新排序时，新的字符串是按照升序排好序的（没要求老字符串排好序）。
解题思路
虚拟赛时其实已经走到了想出正解的路上我在路上了。正解是这样——对于排列p，将所有p[i]到p[i+1]连边，对于q也将所有q[i]和q[i+1]连边，那么每条边就代表前面位置的字母要小于等于后面位置的字母，那对于这个图中的的所有强连通分量，上边的字母应该都是相同的。于是缩点产生一个DAG，这个DAG前面的字母小于等于后面的字母，于是BFS一遍删点，删点的时候给该点赋一个字母，然后字母加一。最后输出答案就好。
虚拟赛时想到的是把p和q扫一遍，然后对于p和q中的一个位置上的不同数字，那么这两个数字代表的新位置之间的字母应该相同，但是这两个位置之间的其他数字也产生了其他一对对位置，然后复杂度就上去了……乱七八糟的各种没想清楚。
源代码
#include<queue>
#include<cstdio>
#include<algorithm>
const int MAXN=2e5+5;
int n,k;
struct Edge{
int nxt,to;
}e[MAXN<<2],e2[MAXN<<2];
int head[MAXN],cnt=1,head2[MAXN],cnt2=1;
inline void add(int u,int v)
{
e[cnt]={head[u],v};
head[u]=cnt++;
}
inline void add2(int u,int v)
{
e2[cnt2]={head2[u],v};
head2[u]=cnt2++;
}
int num=0,id[MAXN];//强连通分量数量
int ru[MAXN];//强连通分量的入度
int ind=1,dfn[MAXN],low[MAXN];
int stack[MAXN],top=0;
bool instack[MAXN];
void dfs(int u)
{
dfn[u]=low[u]=ind++;
stack[top++]=u;
instack[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(!dfn[v])
{
dfs(v);
low[u]=std::min(low[u],low[v]);
}
else if(instack[v]) low[u]=std::min(low[v],low[u]);
}
if(dfn[u]==low[u])
{
int v;
num++;
do{
v=stack[--top];
instack[v]=0;
id[v]=num;
}while(u!=v);
}
}
char ans[MAXN];
void bfs()
{
std::queue<int> q;
for(int u=1;u<=num;u++) if(!ru[u]) q.push(u);
char x='a';
while(!q.empty())
{
int u=q.front();
ans[u]=x;
if(x!='z') x++;
q.pop();
for(int i=head2[u];i;i=e2[i].nxt)
{
int v=e2[i].to;
ru[v]--;
if(!ru[v]) q.push(v);
}
}
}
int main()
{
// freopen("test.in","r",stdin);
scanf("%d%d",&n,&k);
for(int x=0;x<2;x++)
{
int temp;
scanf("%d",&temp);
for(int i=1,j;i<n;i++)
{
scanf("%d",&j);
add(temp,j);
temp=j;
}
scanf("%d",&temp);
for(int i=1,j;i<n;i++)
{
scanf("%d",&j);
add(temp,j);
temp=j;
}
}
for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i);//6>5>4>3>2>1
if(num<k)
{
puts("NO");
return 0;
}
for(int u=1;u<=n;u++)
{
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(id[u]!=id[v]) add2(id[u],id[v]),ru[id[v]]++;
}
}
puts("YES");
bfs();
for(int i=1;i<=n;i++)
{
putchar(ans[id[i]]);
}
return 0;
}