•题意
给你两个数组 p,q ，分别存放 1~n 的某个全排列；
让你根据这两个数组构造一个字符串 S，要求：
(1)$\forall i \in [1,n-1],S_{pi}\leq S _{pi+1} ,\forall i \in [1,n-1],S_{qi} \leq S _{qi+1}$
(2)字符串 S 至少包含 k 个不同的小写字母；
•思路
类似于牛客第五场的H
不过由于这个不知道字母是什么，需要利用强联通分解，
把属于同一个强联通块的位置置于同一个字母，
然后根据前后关系建图连边
•代码
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof a)
const int maxn=2e5+;
int n,m;
int a[maxn];
struct Edge
{
int to,next;
}G[maxn*];
int head[maxn],cnt;
void addEdge(int u,int v)
{
G[++cnt].to=v;
G[cnt].next=head[u];
head[u]=cnt;
} int col[maxn];
struct SCC///强联通分量分解
{
bool vis[maxn];
vector<int> vs; void DFS(int u)
{
vis[u]=true;
for(int i=head[u];i;i=G[i].next)
{
int v=G[i].to;
if(!(i&)||vis[v])
continue;
DFS(v);
}
vs.push_back(u);
} void REDFS(int u,int k)
{
vis[u]=true;
col[u]=k;
for(int i=head[u];i;i=G[i].next)
{
int v=G[i].to;
if((i&)||vis[v])
continue;
REDFS(v,k);
}
} int scc()
{
vs.clear();
mem(vis,false);
for(int i=;i<=n;i++)
if(!vis[i])
DFS(i); mem(vis,false);
int k=;
for(int i=vs.size()-;i>=;i--)
if(!vis[vs[i]])
REDFS(vs[i],++k); return k;
}
}_scc; Edge newG[maxn*];
int head2[maxn];
void addnew(int u,int v)
{
newG[++cnt].to=v;
newG[cnt].next=head2[u];
head2[u]=cnt;
}
int Indu[maxn];
char ch[maxn];
queue<int >q;
void topsort(int k)///拓扑排序
{
while(!q.empty())
q.pop();
for(int i=;i<=k;i++)
if(!Indu[i])
q.push(i); int now=;
while(!q.empty())
{
int u=q.front();
ch[u]='a'+now;
///>=m个不同字母,那就正好m个，后面的都置为同一个
if(now<m-)
now++;
q.pop();
for(int i=head2[u];i;i=newG[i].next)
{
int v=newG[i].to;
Indu[v]--;
if(!Indu[v])
q.push(v);
}
}
}
int main()
{
cin>>n>>m;
for(int i=;i<=;i++)
{
for(int j=;j<=n;j++)
cin>>a[j];
for(int j=;j<=n-;j++)
{
addEdge(a[j],a[j+]);
addEdge(a[j+],a[j]);
}
}
int k=_scc.scc();
if(k<m)
puts("NO");
else
{
puts("YES");
cnt=; ///缩点，把每一个联通快看做一个点
///利用点col[i]之间的关系建图,跑拓扑序
for(int u=;u<=n;u++)
{
for(int i=head[u];i;i=G[i].next)
{
int v=G[i].to;
if(!(i&)||col[u]==col[v])
continue;
addnew(col[u],col[v]);
Indu[col[v]]++;
}
}
topsort(k); for(int i=;i<=n;i++)
cout<<ch[col[i]];
}
}