xjbYY了一下竟然就艹过去了……

如果说是我们知道了每个点出发能得到的串有多少个，我们就能用类似树上求\(k\)大的求法来搞了。问题来了，怎么知道这个？

我先说一下不重复的情况吧，首先到达这个点就有一种串了，然后我们加上他的出边（注意是转移边！）指向的点的值就行了。重复的情况我们考虑一下\(|Right(x)|\)就能搞出来了

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <queue>
#include <algorithm>
#include <set>
const int maxn = 500005;
const int maxno = maxn * 4;
const int bufsiz = 50 * 1024 * 1024;
typedef long long ll;

int fa[maxno], ch[maxno][26];
int len[maxno];
ll ans[maxno][2], val[maxno];
int rt, last;
int cur;
inline void init_sam() {
  rt = last = 1;
  cur = 1;
  ans[1][0] = ans[1][1] = -1LL;
}
inline int alloc_node(int l = 0, int f = 0) {
  int ret = ++ cur;
  len[ret] = l; fa[ret] = f;
  ans[ret][0] = ans[ret][1] = -1LL;
  return ret;
}
inline int idx(char c) {
  return c - 'a';
}
inline void extend(char cx) {
  int c = idx(cx);
  int np = alloc_node(len[last] + 1);
  val[np] = 1LL;
  int p = last;
  while(p && !(ch[p][c])) ch[p][c] = np, p = fa[p];
  if(!p) {
    fa[np] = rt;
  } else {
    int q = ch[p][c];
    if(len[q] == len[p] + 1) {
      fa[np] = q;
    } else {
      int nq = alloc_node(len[p] + 1, fa[q]);
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      fa[q] = fa[np] = nq;
      while(p && ch[p][c] == q) ch[p][c] = nq, p = fa[p];
    }
  }
  last = np;
}
int lc[maxno], rb[maxno];
inline void add_edge(int c, int f) {
  rb[c] = lc[f];
  lc[f] = c;
}
void dfs_1(int x) {
  for(int i = lc[x]; i; i = rb[i]) {
    dfs_1(i);
    val[x] += val[i];
  }
}
void dfs_2(int x) {
  if(ans[x][0] != -1LL) return;
  ans[x][0] = 1LL; ans[x][1] = val[x];
  for(int c = 0; c < 26; c ++) {
    int v = ch[x][c];
    if(v) {
      dfs_2(v);
      ans[x][0] += ans[v][0];
      ans[x][1] += ans[v][1];
    }
  }
}
inline void process() {
  for(int i = 2; i <= cur; i ++) {
    add_edge(i, fa[i]);
  }
  dfs_1(1); dfs_2(1);
#ifdef LOCAL
  for(int i = 1; i <= cur; i ++) {
    printf("ans[%d] : (%lld, %lld)\n", i, ans[i][0], ans[i][1]);
  }
#endif
}
char ret[maxno];
void search(ll k, int typ) {
  static ll val_0[maxno];
  for(int i = 1; i <= cur; i ++) {
    val_0[i] = 1;
  }
  ll *self[2] = {val_0, val};
  k += self[typ][1];
  if(k > ans[1][typ]) {
    ret[0] = '-', ret[1] = '1';
    return;
  }
  int cnt = 0;
  int u = 1;
  while(k > self[typ][u]) {
    int used = 0;
    k -= self[typ][u];
    for(int c = 0; c < 26; c ++) {
      int v = ch[u][c];
      if(!v) continue;
      used ++;
      if(k > ans[v][typ]) {
        k -= ans[v][typ];
      } else {
        ret[cnt ++] = c + 'a';
#ifdef LOCAL
        printf("Towardsing %d with %c\n", v, c + 'a');
        printf("k : %lld\n", k);
#endif
        u = v; break;
      }
    }
    // if(used == 0) break;
  }
}

int main() {
  static char S[maxn];
  scanf("%s", S); int n = strlen(S);
  int typ; ll k; scanf("%d%lld", &typ, &k);
  init_sam();
  for(int i = 0; i < n; i ++) {
    extend(S[i]);
  }
  process();
  search(k, typ);
  puts(ret);
  return 0;
}

• 相关文章
• 全局相关文章