思路线段树, 维护在 $p$ 数组中有哪些元素相同。

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, a[N], color[N], mp[N], k, x, tot;

struct TREE{
  struct Node{
    int l, r, data;
  }t[4 * N];
  void renew(int p){
    t[p].data = max(t[p * 2].data, t[p * 2 + 1].data);
  }
  void build(int p, int l, int r){
    t[p].l = l, t[p].r = r;
    if(l == r){
      t[p].data = 0;
      return;
    }
    int mid = (l + r) >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    renew(p);
  }
  void updata(int p, int l, int x){
    if(t[p].l == t[p].r){
      t[p].data = max(t[p].data, x);
      return;
    }
    int mid = (t[p].l + t[p].r) >> 1;
    if(l <= mid){
      updata(p * 2, l, x);
    }
    else{
      updata(p * 2 + 1, l, x);
    }
    renew(p);
  }
  int getmax(int p, int l, int r){
    if(t[p].l >= l && r >= t[p].r){
      return t[p].data;
    }
    int mid = (t[p].l + t[p].r) >> 1, sum = 0;
    if(l <= mid){
      sum = max(sum, getmax(p * 2, l, r));
    }
    if(r > mid){
      sum = max(sum, getmax(p * 2 + 1, l, r));
    }
    return sum;
  }
}tree;

int main(){
  cin >> n >> k;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
  }
  tree.build(1, 1, n);
  for(int i = 1; i <= n; ++i){
    cin >> x;
    mp[x] = i;
  }
  for(int i = 1; i <= n; ++i){
    tree.updata(1, mp[a[i]], i);
  }
  for(int i = 1; i <= n;){
    int now = tree.getmax(1, 1, mp[a[i]]);
    for(; i <= now; ++i){
      color[a[i]] = tot;
    }
    tot++;
  }
  if(tot < k){
    cout << "NO";
  }
  else{
    cout << "YES\n";
    for(int i = 1; i <= n; ++i){
      cout << char(min(k - 1, color[i]) + 'a');
    }
  }
  return 0;
}