CF-EDU30-F. Forbidden Indices

题目：F. Forbidden Indices 

　题意：给你长度为 \(n\) 的字符串 \(s\) ，并且标记一些位置为禁止位，定义一个字符串 \(t\) 的权值为：\( |t|*F(t)\) ，其中F表示 \(t\) 在 \(s\) 中出现，且不以禁止位结尾的次数。

算法：

　字符串、后缀数组、单调栈、贪心

题解：

　考虑把字符串调转，这样就变成了无法以禁止位开头。

　答案的来源有两种：

　　（1）字符串 \(t\) 只出现了一次，这个时候当然是直接取后缀最优【此时最长】

　　（2）字符串 \(t\) 至少出现了两次，这个时候可以想到height数组，我们把相邻的两个后缀绑在一起，得到 \(lcp\)，这是最优的（这一步有贪心的思想）。我们考虑使用单调栈扩展这个 \(lcp\)的区间 \([L,R]\) ，就像是二维最大矩阵那道例题一样【或者是柱状图最大矩阵】。　

　做法：直接后缀排序，来源一没什么细节，直接写。

　重点考虑来源二，我们需要去掉那些禁止位的后缀再做单调栈，使用前缀和可以去掉禁止位的影响，所以需要额外维护一个 \(len\) 数组，表示 \(lcp\)的长度，最后相邻两个后缀的 \(lcp\) 对答案的影响为：\( sum[R[i]] - sum[L[i] - 1] ) * len[i] \)。

代码：

const int maxn = 2e5 + 17, maxm = 3e5 + 11, inf_int = 0x3f3f3f3f;
// 注意，inf_int < 2^30, (1<<31)已经超了int
const ll inf_ll = 0x3f3f3f3f3f3f3f, mod = 1e9L + 7;
const double eps = 1e-6;

int n, ork[maxn], rk[maxn], sa[maxn], osa[maxn];
int L[maxn], R[maxn], ct[maxn], ht[maxn], len[maxn];
char s[maxn], b[maxn];

inline bool cmp(int x, int y, int d) {
  if (ork[x] != ork[y]) return false;
  if (x + d > n || y + d > n) return x + d > n && y + d > n;
  return ork[x + d] == ork[y + d];
}

inline void build() {
  int lim = 128, top = 0;
  for (int i = 1; i <= n; i++) ct[rk[i] = s[i]]++;
  for (int i = 1; i <= lim; i++) ct[i] += ct[i - 1];
  for (int i = 1; i <= n; i++) sa[ct[rk[i]]--] = i;
  for (int d = 1; d < n; lim = top, d <<= 1) {
    top = 0;
    for (int i = n - d + 1; i <= n; i++) osa[++top] = i;
    for (int i = 1; i <= n; i++)
      if (sa[i] > d) osa[++top] = sa[i] - d;
    for (int i = 0; i <= lim; i++) ct[i] = 0;
    for (int i = 1; i <= n; i++) ct[rk[i]]++;
    for (int i = 1; i <= lim; i++) ct[i] += ct[i - 1];
    for (int i = n; i; i--) sa[ct[rk[osa[i]]]--] = osa[i];
    memcpy(ork, rk, sizeof(rk)), top = 0;
    for (int i = 1; i <= n; i++)
      rk[sa[i]] = (i > 1 && cmp(sa[i], sa[i - 1], d)) ? top : ++top;
    if (top == 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;
  }
}

inline void solve() {
  cin >> n >> s + 1 >> b + 1;
  reverse(s + 1, s + 1 + n);
  reverse(b + 1, b + 1 + n);
  // cout << b + 1 << endl;
  build(), me(ct, 0), me(len, inf_int);
  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    L[i] = 1, R[i] = n, ct[i] = ct[i - 1] + (b[sa[i]] == '0');
    if (b[sa[i]] == '0') ans = max(ans, n - sa[i] + 1ll);
  }
  stack stk;
  for (int i = 2, las = 1; i <= n; i++) {
    if (b[sa[i]] == '1') continue;
    for (int j = las + 1; j <= i; j++) len[i] = min(len[i], ht[j]);
    while (stk.size() && stk.top().fi > len[i])
      R[stk.top().se] = i - 1, stk.pop();
    if (stk.size()) L[i] = stk.top().se;
    stk.push(mp(len[i], i)), las = i;
  }
  for (int i = 2; i <= n; i++)
    if (b[sa[i]] == '0') ans = max(ans, (ll)(ct[R[i]] - ct[L[i] - 1]) * len[i]);
  cout << ans << endl;
}