自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:29:08，当前版本为作者最后更新于2021-12-29 11:24:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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
*/