BZOJ 4199 品酒大会

题意：

给定一个长度为\(n\)的串。\(n\leq3 \times 10^5\)

对于\(\forall i\in [0,n-1]\)，求出\(LCP(suf(k),suf(j))==i\)的数量并且求出其最大的权值积。

https://www.lydsy.com/JudgeOnline/problem.php?id=4199

Sol：

单调栈求出每个\(Height[i]\)能延伸的范围，然后乘起来，注意\(Height[i]=0\)时不能这么求

原因是会有多个\(0\)，每个\(0\)都会控制最小左边界和最大右边界，也就是说会算多次但是不对。

第二问直接\(ST\)表然后对于每个点\(i\)求左右的最大最小然后匹配一下

数据比较弱，明显都没卡对于一个\(i\)，这个\(i\)是划分到左区间还是划分到右区间。

upd ： 并查集做法好像 快很多的样子，好像也很好写\(Merge\)有点烦

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<algorithm>
const int N = 1e5 + 5e4 + 7;
const int lim = 3e5;
typedef long long LL;
inline LL max(LL a, LL b){return a > b ? a : b;}
inline LL min(LL a, LL b){return a > b ? b : a;}
int x[N*2], y[N*2], sa[N*2], rk[N*2], c[N*2];
int m = lim, n; int het[N*2], qlog[N*2];LL st[20][N*2][2];
//#define R register
char ss[N*2];
inline void getSA() {
  for (int i = 0; i <= m; i++) c[i] = 0;
  for (int i = 1; i <= n; i++) c[x[i] = ss[i] - 'a' + 1]++;
  for (int i = 1; i <= m; i++) c[i] += c[i - 1];
  for (int i = 1; i <= n; i++) sa[c[x[i]]--] = i;
  for (int siz = 1, p = 0; siz <= n; siz <<= 1, p = 0) {
    for (int i = n - siz + 1; i <= n; i++) y[++p] = i;
    for (int i = 1; i <= n; i++) if (sa[i] > siz) y[++p] = sa[i] - siz;
    for (int i = 0; i <= m; i++) c[i] = 0;
    for (int i = 1; i <= n; i++) c[x[y[i]]]++;
    for (int i = 1; i <= m; i++) c[i] += c[i - 1];
    for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
    std :: swap(x, y), x[sa[1]] = 1, p = 1;
    for (int i = 2; i <= n; i++) x[sa[i]] = 
      (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + siz] == y[sa[i - 1] + siz]) ? p : ++p;
    if (p == n) break; m = p;
  } int k = 0;
  memset(het, 0, sizeof(het));
  for (int i = 1; i <= n; i++) rk[sa[i]] = i;
  for (int i = 1; i <= n; i++) if (rk[i] != 1) {
    if (k) k--;
    int j = sa[rk[i] - 1];
    while(j + k <= n && i + k <= n && ss[i + k] == ss[j + k]) k++;
    het[rk[i]] = k;
  } 
} LL inf = (LL)(1e9 + 7); LL A[N*2];
inline void getST() {
  qlog[1] = 0, memset(st, 0, sizeof(st));
  for (int i = 2; i <= lim; i++) qlog[i] = qlog[i / 2] + 1;
  for (int i = 1; i <= n; i++) 
    st[0][i][0] = st[0][i][1] = A[sa[i]];
  // 0 最大  1最小
  int logw = qlog[n];
  for (int i = 1; i <= logw; i++) for (int j = 1; j + (1 << i) - 1 <= n; j++) {
    st[i][j][0] = max(st[i - 1][j][0], st[i - 1][j + (1 << (i - 1))][0]);
    st[i][j][1] = min(st[i - 1][j][1], st[i - 1][j + (1 << (i - 1))][1]);
  }
} LL BASE = -(inf * inf);
inline LL query(int x, int y, int cal) { 
  LL ans1 = BASE, ans2 = BASE;
  if (x > y) return 1;
  else if (x == y) return A[sa[x]];
  int logw = qlog[y - x + 1];
  ans1 = max(st[logw][x][0], st[logw][y - (1 << logw) + 1][0]);
  ans2 = min(st[logw][x][1], st[logw][y - (1 << logw) + 1][1]);
  return cal ? ans1 : ans2;
}
int stack[N*2], top;int R[N*2], L[N*2];
void prog() {
  stack[++top] = 1;
  for (int i = 2; i <= n; i++) {
    while (top && het[stack[top]] >= het[i]) R[stack[top--]] = i;
    L[i] = stack[top], stack[++top] = i;
  } while (top) R[stack[top--]] = n + 1; 
} LL ans1[2*N]; LL ans2[2*N];
inline void solve1() {
  LL res = -(LL)(inf * inf); 
  for (int i = 0; i <= n; i++) ans2[het[i]] = res;
  for (int i = 2; i <= n; i++) {
    if (!het[i]) continue; 
    ans1[het[i]] += (LL)((LL)R[i] - i) * ((LL)i - L[i]);
    if (R[i] - L[i] <= 1) continue;
    LL ret1, ret2, ret3, ret4; ret1 = ret2 = ret3 = ret4 = BASE;
    if (R[i] - 1 - (i + 1) >= 0) 
      ret1 = query(L[i], i, 1) * query(i + 1, R[i] - 1, 1),
      ret3 = query(L[i], i, 0) * query(i + 1, R[i] - 1, 0);
    if (i - 1 - L[i] >= 0) 
      ret2 = query(L[i], i - 1, 1) * query(i, R[i] - 1, 1),
      ret4 = query(L[i], i - 1, 0) * query(i, R[i] - 1, 0);
    ret1 = max(ret1, ret3), ret2 = max(ret2, ret4);
    ans2[het[i]] = max(max(ans2[het[i]], ret1), ret2);
  }
  ans1[0] = (LL(((LL)n * ((LL)n - 1LL)) / 2LL));
  for (int i = 2; i < n; i++) {
    LL ret1 = max(query(1, i, 1) * query(i + 1, n, 1),
      query(1, i - 1, 1) * query(i, n, 1)),
    ret2 = max(query(1, i, 0) * query(i + 1, n, 0), 
      query(1, i - 1, 0) * query(i, n, 0));
    ans2[0] = max(max(ans2[0], ret1), ret2);
  }
  for (int i = n - 1; i >= 1; i--) {
    ans1[i] = ans1[i + 1] + ans1[i];
    if (ans2[i + 1] != 0) ans2[i] = max(ans2[i + 1], ans2[i]);
  }
  for (int i = 0; i < n; i++) if (ans2[i] == BASE) ans2[i] = 0;
  for (int i = 0; i < n; i++) printf ("%lld %lld\n", ans1[i], ans2[i]);
}
int main() {
  scanf("%d", &n); scanf ("%s", ss + 1);
  for (int i = 1; i <= n; i++) scanf("%lld", &A[i]);
  getSA(), prog(), getST();
  solve1();
return 0;
}

BZOJ 4199 品酒大会

原文：https://www.cnblogs.com/cjc030205/p/11638089.html