https://www.luogu.com.cn/problem/CF1968G2

CF1968G2 Division + LCP (hard version) 题解

前言

这题可以 \(O(n \sqrt{n} \log n)\) 再各种优化做，算法是二分、哈希（不知道包不包含根号分治，但是有用到根号分治的思想）。

如果读题解有些抽象的话可以看代码辅助理解。

题意转化

由于是从第一个位置开始分段，所以问题就是在字符串中，选出 \(k(l \le k \le r)\) 个不相交的且完全相同的子段，不过必须选择从头开始的一个子段，求最长长度。

思路

Easy Version

如果只用求对一个 \(k\) 求答案。

可以二分答案，然后在内部可以 \(O(n)\) 地 check 答案。

check 如何 \(O(n)\) 做呢？第一个位置开头的子段必须选择，贪心地，第一个位置选择的子段开始，从当前子段的结尾向后找到最近完全相等的子段，判断子段相等可以使用哈希。

时间复杂度 \(O(n \log n)\)。

Hard Version

想了很多种做法发现都不好做，猜一猜时间复杂度，假设时间复杂度带根号，没想到完全可做。

Hard Version 就是有多个 \(k\) 需要同时求解，我么不如直接求所有 \(1 \le k \le n\) 的答案。

• 对于 \(1 \le k \le \sqrt{n}\) 的 \(k\)，用 Easy Version 的做法求解，时间复杂度 \(O(n \sqrt{n} \log n)\)。
• 对于 \(\sqrt{n} < k \le n\) 的 \(k\)，则分段后最长的段最长 \(\sqrt{n}\)，所以其答案必定小于等于 \(\sqrt{n}\)。
  • 枚举每个长度 \(l(1 \le l \le \sqrt{n})\)，使用 Easy Version 中 check 的做法来求最多可以分几段，然后前缀和一下。
  • 时间复杂度 \(O(n \sqrt{n})\)。

两种做法合并起来即可。

优化1

发现两种情况处理的时间复杂度不同，一个 \(O(n \log n)\)，另一个 \(O(n)\)。则我们可以平衡一下。

显然第一种做法给 \(1 \le k \le B\) 的直接求解，第二种做法就是长度小于等于 \(\frac{n}{B}\)。

这个 \(B\) 显然可以设为 \(200\)。

优化2

对于第一种做法，发现 \(k\) 从 \(1\) 到 \(B\) 对应的答案是不增的，所以二分答案时的上界可以由 \(ans_{k-1}\) 决定。

优化3

对于第一种做法，发现答案有很长一段连续，所以在二分前先 check \(ans_{k-1}\)，若可以则 \(ans_k = ans_{k-1}\)，否则再二分答案。

Code

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using Pair = pair<LL, LL>;

const int MAXN = 2e5 + 3;
const LL mod = 998244353;
const Pair B = {37, 47}; // 使用双哈希

int n, L, R, ans[MAXN];
char s[MAXN];
Pair Hash[MAXN], Bpow[MAXN];

Pair H(int l, int r){ // 求区间哈希值
  return {(Hash[r].first - Hash[l-1].first * Bpow[r-l+1].first % mod + mod) % mod,
           (Hash[r].second- Hash[l-1].second* Bpow[r-l+1].second% mod + mod) % mod};
}

bool check(int D, int k){ // 二分中的 check 函数
  int cnt = 0;
  for(int i = 1; i + D - 1 <= n; ){
    while(i + D - 1 <= n && H(i, i + D - 1) != H(1, D)) i++;
    cnt += i + D - 1 <= n && H(i, i + D - 1) == H(1, D), i = i + D;
    if(cnt >= k) return 1;
  }
  return 0;
}

void work(){
  cin >> n >> L >> R;
  for(int i = 1; i <= n; i++){
    cin >> s[i];
  }
  Bpow[0] = {1, 1};
  for(int i = 1; i <= n; i++){ // 预处理前缀哈希
    Bpow[i] = {Bpow[i-1].first * B.first % mod, Bpow[i-1].second* B.second% mod};
    Hash[i] = {(Hash[i-1].first * B.first % mod + s[i] - 'a' + 1) % mod,
               (Hash[i-1].second* B.second% mod + s[i] - 'a' + 1) % mod};
  }
  for(int i = 1; i <= n; i++) ans[i] = 0;
  for(int D = min(n, 1000); D >= 1; D--){ // 求解 200 < k <= n 的答案
    int mx = 0;
    for(int i = 1; i + D - 1 <= n; ){ // 类似 check 函数
      while(i + D - 1 <= n && H(i, i + D - 1) != H(1, D)) i++;
      mx += i + D - 1 <= n && H(i, i + D - 1) == H(1, D), i = i + D;
    }
    ans[mx] = max(ans[mx], D); // 前缀和
  }
  for(int i = n - 1; i >= 1; i--) ans[i] = max(ans[i], ans[i + 1]);
  ans[0] = n;
  for(int k = 1; k <= min(n, 200); k++){ // 求解 1 <= k <= 200 的答案
    int l = 0, r = ans[k - 1];
    if(check(r, k)) l = r;
    while(l < r){
      int mid = (l + r + 1) >> 1;
      if(check(mid, k)){
        l = mid;
      }else r = mid - 1;
    }
    ans[k] = max(ans[k], l);
  }
  for(int i = L; i <= R; i++) cout << ans[i] << " ";
  cout << "\n";
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  int T;
  cin >> T;
  while(T--) work();
  return 0;
}