题解：P11291 【MX-S6-T3】「KDOI-11」简单的字符串问题 2

提供一个巨大复杂的场内做法。

由于允许

R_i

为空，所以对于子串

T_{[l, r]}

，记

k'

为其至少需要多少个好的字符串拼接而成，则

\forall k \in [k', K]

，

(l, r, k)

均为好的三元组。

考虑贪心求解

k'

：记

T_{[i, |T|]}

与

n

个串的

\text{lcp}

的最大值为

p_i

，从

l

开始每次跳最远的右端点即可求解。

具体地，记

ans_{l, i}

表示

T_{[l, i]}

对应的

k'

。为了对于一个左端点

l

求出所有

[l, r]

的

ans

，考虑维护一个

t

，初始为

l - 1

，每次在

[l, t + 1]

范围内取一个

i

，最大化

q = i + p_i

，然后令

ans_{l, [t + 1, q - 1]} \gets \text{steps}

，再令

t \gets q - 1

，其中

\text{steps}

为操作次数，如果

q - 1 \leq t

那么提前终止，否则在

q = |T| + 1

时终止。

容易发现从初始状态跳跃一次之后，剩余的问题是一个几乎独立的子问题。形式化地讲，先判掉两种边界情况，第一种是

l + p_l = |T| + 1

的情况，此时有

ans_{l, *} = 1

，第二种是

p_l = 0

的情况，此时不妨令

ans_{l, *} = K + 1

。对于一般情况，我们求出一个

i \in [l + 1, l + p_l]

，最大化

i + p_i

（多个任取其一），那么可以用下述方式计算

ans

序列：

令 $ans_{l, j} \gets \min(ans_{i, j} + 1, K + 1), j \geq i$ 。
然后令 $ans_{l, j} \gets 1, l \leq j < l + p_l$ 。

为了更有利于后续处理，我们将这个过程精细化一点：

显然 $ans$ 序列是不降的，记 $x$ 为最小的位置满足 $ans_{i, x} = K + 1$ ，若没有则为 $|T| + 1$ 。假定 $ans$ 序列初始全 $0$ 。
令 $ans_{l, j} \gets ans_{i, j}, j \geq i$ 。
对 $ans_{l, [l, i - 1]}$ 加 $1$ 。
对 $ans_{l, [l + p_l, x - 1]}$ 加 $1$ ，如果 $l + p_l \leq x - 1$ 。

这意味着，我们只需要支持将

ans_l

继承

ans_i

，以及区间加两种操作，很难不想到用线段树处理。乍一看继承操作得用主席树，但是事实上我们可以把继承操作建树，从而离线处理掉。

具体来说，对于每个“

ans_l

继承

ans_i

”的操作，我们连一条

i \to l

的边，这样我们可以得到一个森林。考虑从根结点开始 dfs，每进入一个点时，我们分两种情况讨论：

点是根结点：这对应了上文 $ans_{l, *} = 1$ 或 $ans_{l, *} = K + 1$ 的情况，直接在线段树上对区间 $[l, |T|]$ 区间加 $1/K + 1$ 即可。
否则：线段树二分出上文中的 $x$ ，然后对 $[l, i - 1]$ 与 $[l + p_l, x - 1]$ 区间加 $1$ 即可。

当我们从一个点回溯时，只需要撤销加入时的贡献即可。这样一来我们可以做到

\Theta(|T| \log |T|)

求出所有

ans

。

考虑统计答案。统计好的三元组数量是容易的，对于每个

l

合法的三元组数为

\sum \limits_{r \geq l} (K + 1 - ans_{l, r}) = (|T| - l + 1)(K + 1) - \sum \limits_{r \geq l} ans_{l, r}

，而

\sum ans_{l, r}

容易用线段树求出。对所有

l

的答案求和即可。

第二问会棘手一些，考虑将

l \leq i \leq r

这一限制容斥，即总三元组数减去

[l, r] \subseteq [1, i - 1]

的三元组数，再减去

[l, r] \subseteq [i + 1, |T|]

的三元组数。

[l, r] \subseteq [i + 1, |T|]

的三元组数是容易计算的，实质上就是求每个左端点

l

对应的三元组数量，直接用上一问中的求法即可。

[l, r] \subseteq [1, i - 1]

的限制下，我们需要对每个

r

求出三元组数。实质上只需对于所有

ans_{*, r}

求和，可以使用线段树维护历史和解决。

至此我们以

\Theta(|T| \log |T|)

但是巨大常数的复杂度解决了问题。

关于代码：作者偷懒用了二分哈希求 $\text{lcp}$ ，所以会多出来一个 $\Theta(n |T| \log|S|)$ 的复杂度，当然肯定是可以用字符串算法做到更优的。

CPP

// Such a destiny was not desired.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int N = 5e5 + 5, Maxl = 5e4 + 5;
int n, K;
char S[12][Maxl]; int LS[12];
char T[N]; int m;
ll res;

constexpr int mod[2] = {998244353, 1004535809};
constexpr int base[2] = {31, 29};
int Pow[2][N];
inline pair<int, int> add(pair<int, int> H, char ch) {
  int x = H.first, y = H.second;
  x = (1ll * x * base[0] + (ch - 'a' + 1)) % mod[0];
  y = (1ll * y * base[1] + (ch - 'a' + 1)) % mod[1];
  return {x, y};
}
struct Hash {
  char *s; int n;
  vector<pair<int, int>> w;
  inline void build() {
    w.resize(n + 1);
    for(int i = 1; i <= n; i++) {
      w[i] = add(w[i - 1], s[i]);
    }
  }
  inline pair<int, int> getH(int l, int r) {
    int x = w[r].first, y = w[r].second;
    x = (mod[0] + x - 1ll * w[l - 1].first * Pow[0][r - l + 1] % mod[0]) % mod[0];
    y = (mod[1] + y - 1ll * w[l - 1].second * Pow[1][r - l + 1] % mod[1]) % mod[1];
    return {x, y};
  }
} HS[12], HT;

int p[N];

struct SparseTable {
  pair<int, int> st[19][N];
  inline void build() {
    for(int i = 1; i <= m; i++) {
      st[0][i] = {p[i] + i, i};
    }
    for(int i = 1; i <= 18; i++) {
      for(int j = 1; j + (1 << i) - 1 <= m; j++) {
        st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
      }
    }
  }
  inline pair<int, int> query(int l, int r) {
    int L = __lg(r - l + 1);
    return max(st[L][l], st[L][r - (1 << L) + 1]);
  }
} st;

// constexpr int maxn = 1000;
// int ans[maxn][maxn];
ll sumL[N], sumR[N];

vector<int> G[N];
int op[N], to[N];

struct SegmentTree {
  int t;
  ll tagc[N << 2], taga[N << 2], c[N << 2], a[N << 2], maxa[N << 2];
  inline void pushdown(int pos, int l, int r) {
    if(taga[pos] == 0 && tagc[pos] == 0) return;
    int mid = (l + r) >> 1;
    c[pos << 1] += tagc[pos] * (mid - l + 1);
    c[pos << 1 | 1] += tagc[pos] * (r - mid);
    a[pos << 1] += taga[pos] * (mid - l + 1);
    a[pos << 1 | 1] += taga[pos] * (r - mid);
    maxa[pos << 1] += taga[pos];
    maxa[pos << 1 | 1] += taga[pos];

    taga[pos << 1] += taga[pos]; 
    taga[pos << 1 | 1] += taga[pos];
    tagc[pos << 1] += tagc[pos];
    tagc[pos << 1 | 1] += tagc[pos];
    tagc[pos] = taga[pos] = 0;
  }
  inline void pushup(int pos) {
    c[pos] = c[pos << 1] + c[pos << 1 | 1]; 
    a[pos] = a[pos << 1] + a[pos << 1 | 1];
    maxa[pos] = max(maxa[pos << 1], maxa[pos << 1 | 1]);
  }
  inline void modify_a(int l, int r, int L, int R, ll k, int pos) {
    if(L <= l && r <= R) {
      a[pos] += (r - l + 1) * k;
      taga[pos] += k;
      maxa[pos] += k;
      return;
    }
    int mid = (l + r) >> 1;
    pushdown(pos, l, r);
    if(L <= mid) modify_a(l, mid, L, R, k, pos << 1);
    if(R > mid) modify_a(mid + 1, r, L, R, k, pos << 1 | 1);
    pushup(pos);
  }
  inline void modify_c(int l, int r, int L, int R, ll k, int pos) {
    if(L <= l && r <= R) {
      c[pos] += (r - l + 1) * k;
      tagc[pos] += k;
      return;
    }
    int mid = (l + r) >> 1;
    pushdown(pos, l, r);
    if(L <= mid) modify_c(l, mid, L, R, k, pos << 1);
    if(R > mid) modify_c(mid + 1, r, L, R, k, pos << 1 | 1);
    pushup(pos);
  }
  inline ll query_a(int l, int r, int L, int R, int pos) {
    if(L <= l && r <= R) return a[pos];
    int mid = (l + r) >> 1; ll ret = 0;
    pushdown(pos, l, r);
    if(L <= mid) ret += query_a(l, mid, L, R, pos << 1);
    if(R > mid) ret += query_a(mid + 1, r, L, R, pos << 1 | 1);
    pushup(pos);
    return ret;
  }
  inline ll query_c(int l, int r, int L, int R, int pos) {
    if(L <= l && r <= R) return c[pos] + t * a[pos];
    int mid = (l + r) >> 1; ll ret = 0;
    pushdown(pos, l, r);
    if(L <= mid) ret += query_c(l, mid, L, R, pos << 1);
    if(R > mid) ret += query_c(mid + 1, r, L, R, pos << 1 | 1);
    pushup(pos);
    return ret;
  }
  inline void modify(int l, int r, int L, int R, int x, int pos = 1) {
    modify_a(l, r, L, R, x, 1);
    modify_c(l, r, L, R, -1ll * t * x, 1);
  }
  inline int get(int l = 1, int r = m, int pos = 1) {
    if(l == r) return l;
    int mid = l + r >> 1; pushdown(pos, l, r);
    if(maxa[pos << 1] == K + 1) return get(l, mid, pos << 1);
    return get(mid + 1, r, pos << 1 | 1);
  }
} sgt;

void dfs(int i) {
  int o;
  if(!to[i]) sgt.modify(1, m, i, m, op[i]);
  else {
    sgt.modify(1, m, i, to[i] - 1, 1);
    o = (sgt.maxa[1] == K + 1 ? sgt.get() : m + 1);
    if(i + p[i] <= o - 1) sgt.modify(1, m, i + p[i], o - 1, 1);
  }
  sgt.t++;
  ll w = 1ll * (m - i + 1) * (K + 1) - sgt.query_a(1, m, i, m, 1);
  sumR[i] = w, res += w;
  // for(int j = i; j <= m; j++) {
  //   sumL[j] += K + 1 - sgt.query_a(1, m, j, j, 1);
  // }
  for(auto u : G[i]) {
    dfs(u);
  }

  if(!to[i]) sgt.modify(1, m, i, m, -op[i]);
  else {
    sgt.modify(1, m, i, to[i] - 1, -1);
    if(i + p[i] <= o - 1) sgt.modify(1, m, i + p[i], o - 1, -1);
  }
}

int main() {
  // freopen("string.in", "r", stdin);
  // freopen("string.out", "w", stdout);
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  
  Pow[0][0] = Pow[1][0] = 1;
  for(int i = 1; i < N; i++) {
    for(int o = 0; o < 2; o++) {
      Pow[o][i] = 1ll * Pow[o][i - 1] * base[o] % mod[o];
    }
  }

  int _; cin >> _ >> n >> K;
  for(int i = 1; i <= n; i++) {
    cin >> S[i] + 1;
    LS[i] = strlen(S[i] + 1);
    HS[i].s = S[i], HS[i].n = LS[i], HS[i].build();
  }
  cin >> T + 1; m = strlen(T + 1);
  HT.s = T, HT.n = m, HT.build();

  for(int i = 1; i <= m; i++) {
    for(int j = 1; j <= n; j++) {
      int l = 1, r = min(m - i + 1, LS[j]), res = 0;
      while(l <= r) {
        int mid = l + r >> 1;
        if(HS[j].w[mid] == HT.getH(i, i + mid - 1)) {
          res = mid;
          l = mid + 1;
        } else {
          r = mid - 1;
        }
      }
      p[i] = max(p[i], res);
    }
  }
  st.build();
  
  // int res = 0;
  for(int i = m; i >= 1; i--) {
    if(p[i] == 0) {
      op[i] = K + 1;
      // fill(ans[i] + i, ans[i] + m + 1, K + 1);
    } else {
      if(i + p[i] > m) op[i] = 1;
      else {
        int t = (st.query(i + 1, i + p[i])).second;
        G[t].push_back(i);
        to[i] = t;
      }
      // for(int j = 1; j <= m; j++) ans[i][j] = ans[t][j] + 1;
      // for(int j = i; j < i + p[i]; j++) ans[i][j] = 1;
    }
    // for(int j = i; j <= m; j++) {
    //   res += max(0, K + 1 - ans[i][j]);
    //   sumL[j] += max(0, K + 1 - ans[i][j]);
    //   sumR[i] += max(0, K + 1 - ans[i][j]);
    // }
  }
  for(int i = m; i >= 1; i--) {
    if(to[i]) continue;
    dfs(i);
  }
  for(int i = 1; i <= m; i++) {
    sumL[i] = 1ll * (K + 1) * i - sgt.query_c(1, m, i, i, 1);
  }

  cout << res << "\n";
  for(int i = 1; i <= m; i++) sumL[i] += sumL[i - 1];
  for(int i = m; i >= 1; i--) sumR[i] += sumR[i + 1];
  for(int i = 1; i <= m; i++) {
    cout << res - sumL[i - 1] - sumR[i + 1] << " \n"[i == m];
  }
}

题解：P11291 【MX-S6-T3】「KDOI-11」简单的字符串问题 2

文章操作

相关推荐

评论

题解：P11291 【MX-S6-T3】「KDOI-11」简单的字符串问题 2