P7361 「JZOI-1」拜神

· · 题解

P7361「JZOI-1」拜神

不错的题目。

建出 s 的后缀数组，考虑一次询问的本质。对于长度 L，它合法当且仅当存在两个位置 p, q \in [l, r - L + 1](p\neq q)，使得 lcp(suf_p, suf_q)\geq L。根据套路，p, q 满足该条件当且仅当若将所有 \geq L 的 ht_i 值对应的两个位置 sa_{i - 1} 与 sa_i 之间连边，则 p, q 在同一连通块。

显然答案满足可二分性，因此着眼于判断一个长度 L 是否合法。借鉴品酒大会的技巧，我们求出 ht 数组后从大到小加入并查集，相当于每次合并两个位置 sa_{i - 1}, sa_i。对于每个长度 L，在线段树 T_L 上记录每个位置 p 的后继 suc_p，表示 suc_p 是大于 p 且和 p 在相同连通块的最小位置。判断合法只需查询 T_L 上 [l, r - L] 的区间最小值是否 \leq r - L + 1。

考虑如何维护 suc_p：启发式合并。为并查集的每个代表元维护一个 set S_i，每次往 S_i 中插入一个数 y，lower_bound 查询 y 的后继 su 与前驱 pr，在线段树上更新 suc_{pr} \gets y 且 suc_y \gets su。由于要储存每个长度的线段树，所以可持久化。

时空复杂度均为线性对数平方。算法是 在线 的。

#include <bits/stdc++.h>
using namespace std;
bool Mbe;
constexpr int N = 5e4 + 5;
int n, q, id[N];
char s[N];
int sa[N], rk[N], ork[N], buc[N], ht[N];
bool cmp(int a, int b, int w) {return ork[a] == ork[b] && ork[a + w] == ork[b + w];}
void build() {
  int m = 1 << 7, p = 0;
  for(int i = 1; i <= n; i++) buc[rk[i] = s[i]]++;
  for(int i = 1; i <= m; i++) buc[i] += buc[i - 1];
  for(int i = n; i; i--) sa[buc[rk[i]]--] = i;
  for(int w = 1; ; w <<= 1, m = p, p = 0) {
    for(int i = n - w + 1; i <= n; i++) id[++p] = i;
    for(int i = 1; i <= n; i++) if(sa[i] > w) id[++p] = sa[i] - w;
    memset(buc, 0, sizeof(buc));
    memcpy(ork, rk, sizeof(rk));
    p = 0;
    for(int i = 1; i <= n; i++) buc[rk[id[i]]]++;
    for(int i = 1; i <= m; i++) buc[i] += buc[i - 1];
    for(int i = n; i; i--) sa[buc[rk[id[i]]]--] = id[i];
    for(int i = 1; i <= n; i++) rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
    if(p == n) break;
  }
  for(int i = 1, k = 0; i <= n; i++) {
    if(k) k--;
    while(s[i + k] == s[sa[rk[i] - 1] + k]) k++;
    ht[rk[i]] = k;
  }
}
int node, R[N], ls[N << 8], rs[N << 8];
unsigned short val[N << 8];
void build(int l, int r, int &x) {
  x = ++node, val[x] = -1;
  if(l == r) return;
  int m = l + r >> 1;
  build(l, m, ls[x]), build(m + 1, r, rs[x]);
}
vector<pair<int, int>> chg; // make_pair(pos, val)
void modify(int pre, int &x, int l, int r) {
  if(chg.empty() || chg.back().first > r) return;
  assert(l <= chg.back().first);
  x = ++node, ls[x] = ls[pre], rs[x] = rs[pre];
  if(l == r) {
    val[x] = chg.back().second;
    chg.pop_back();
    return;
  }
  int m = l + r >> 1;
  modify(ls[pre], ls[x], l, m);
  modify(rs[pre], rs[x], m + 1, r);
  val[x] = min(val[ls[x]], val[rs[x]]);
}
int query(int l, int r, int ql, int qr, int x) {
  if(ql > qr || !x) return N;
  if(ql <= l && r <= qr) return val[x];
  int m = l + r >> 1, ans = N;
  if(ql <= m) ans = query(l, m, ql, qr, ls[x]);
  if(m < qr) ans = min(ans, query(m + 1, r, ql, qr, rs[x]));
  return ans;
}

int fa[N], upd[N], cnt;
set<int> S[N];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void update(int pos, int val) {
  if(!upd[pos]) id[++cnt] = pos;
  upd[pos] = val;
}
void merge(int x, int y) {
  x = find(x), y = find(y);
  if(S[x].size() < S[y].size()) swap(x, y);
  fa[y] = x;
  for(int it : S[y]) {
    auto pt = S[x].lower_bound(it);
    if(pt != S[x].end()) update(it, *pt);
    if(pt != S[x].begin()) update(*--pt, it);
    S[x].insert(it);
  }
  set<int> ().swap(S[y]);
}

bool Med;
int main() {
  fprintf(stderr, "%.4lf\n", (&Mbe - &Med) / 1048576.0);
#ifdef ALEX_WEI
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
#endif
  scanf("%d%d%s", &n, &q, s + 1);
  build();
  build(1, n, R[n]);
  static pair<int, int> p[N];
  for(int i = 1; i <= n; i++) fa[i] = i, S[i].insert(i);
  for(int i = 1; i < n; i++) p[i] = {ht[i + 1], i + 1};
  sort(p + 1, p + n);
  for(int i = n - 1, pt = n - 1; i; i--) {
    cnt = 0, chg.clear();
    while(pt && p[pt].first == i) {
      int q = p[pt].second;
      merge(sa[q - 1], sa[q]), pt--;
    }
    sort(id + 1, id + cnt + 1);
    for(int i = cnt; i; i--) chg.push_back({id[i], upd[id[i]]}), upd[id[i]] = 0;
    if(chg.empty()) R[i] = R[i + 1];
    else modify(R[i + 1], R[i], 1, n);
  }
  for(int i = 1; i <= q; i++) {
    int ql, qr;
    scanf("%d%d", &ql, &qr);
    int l = 0, r = qr - ql;
    while(l < r) {
      int m = l + r + 2 >> 1;
      if(query(1, n, ql, qr - m, R[m]) <= qr - m + 1) l = m;
      else r = m - 1;
    }
    printf("%d\n", l);
  }
  return 0;
}
/*
2022/6/16
start coding at 12:36
finish debugging at 13:08
*/