P2178

题目大意

给你一个字符串 $S$，每个位置都有一个权值 $a_i$。

定义 $p$ 和 $q$ 两个位置 $r$ 相似表示 $S[p\ldots p+r-1]=S[q\ldots q+r-1]$。

对于所有的 $r \in [0,n-1]$ 求：

• 有多少对 $(p,q)$ 是 $r$ 相似的。
• 最大的 $a_p \times a_q$ 满足 $(p,q)$ 是 $r$ 相似的。

解题思路

考虑倒着建 $SAM$，发现 $(p,q)$ 是 $r$ 相似的等价于存在一个 $endpos$ 等价类包含 $p$ 和 $q$，并且 $minlen\le r \le len$。

有了这个我们就可以计算每一个 $endpos$ 等价类对答案的贡献。

• 对于第一个问题，一个 $endpos$ 等价类对答案的贡献为：$[minlen,len]$ 区间都加上 $\dbinom{size}{2}$。

• 对于第二个问题，一个 $endpos$ 等价类对答案的贡献为：$[minlen,len]$ 区间都与 $\max_{p,q\in endpos, p\neq q}(a_p a_q)$ 取 $\max$。

然后类似于树形dp，用两颗线段树维护一下答案即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long; using vi = vector<int>;
#define rep(i, a, b) for(auto i = (a); i <= (b); i++)
#define per(i, a, b) for(auto i = (a); i >= (b); i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define mcpy(a, b) memcpy(a, b, sizeof(a))

mt19937 rnd(random_device{}());
const ll mod = 998244353, inf = 1e18;
const int iinf = 1e9;

const int N = 3e5 + 10;
int n;
char s[N];
ll a[N], res1[N], res2[N];

struct SegmentTreeSum {
  static const int N = 3e5 + 10;
  ll t[N << 2], lz[N << 2];
  #define lc (x << 1)
  #define rc (x << 1 | 1)
  #define mid (l + r >> 1)
  void up(int x) { t[x] = t[lc] + t[rc]; }
  void cg(int x, int l, int r, ll v) { t[x] += v * (r - l + 1), lz[x] += v; }
  void down(int x, int l, int r) {
    if(lz[x])
      cg(lc, l, mid, lz[x]),
      cg(rc, mid + 1, r, lz[x]),
      lz[x] = 0;
  }
  void update(int x, int l, int r, int a, int b, ll v) {
    if(l > b || a > r) return;
    if(a <= l && r <= b) return cg(x, l, r, v);
    down(x, l, r);
    update(lc, l, mid, a, b, v), update(rc, mid + 1, r, a, b, v);
    up(x);
  }
  void getall(ll *a, int x, int l, int r) {
    if(l == r) a[l] = t[x];
    else down(x, l, r), getall(a, lc, l, mid), getall(a, rc, mid + 1, r);
  }
  #undef lc
  #undef rc
  #undef mid
} sgtSum;

struct SegmentTreeMax {
  static const int N = 3e5 + 10;
  ll t[N << 2] = {-inf}, lz[N << 2];
  #define lc (x << 1)
  #define rc (x << 1 | 1)
  #define mid (l + r >> 1)
  void build(int x, int l, int r) {
    t[x] = lz[x] = -inf;
    if(l != r) build(lc, l, mid), build(rc, mid + 1, r);
  }
  void up(int x) { t[x] = max(t[lc], t[rc]); }
  void cg(int x, ll v) { t[x] = max(t[x], v), lz[x] = max(lz[x], v); }
  void down(int x) { cg(lc, lz[x]), cg(rc, lz[x]), lz[x] = -inf; }
  void update(int x, int l, int r, int a, int b, ll v) {
    if(l > b || a > r) return;
    if(a <= l && r <= b) return cg(x, v);
    down(x); update(lc, l, mid, a, b, v), update(rc, mid + 1, r, a, b, v); up(x);
  }
  void getall(ll *a, int x, int l, int r) {
    if(l == r) a[l] = t[x];
    else down(x), getall(a, lc, l, mid), getall(a, rc, mid + 1, r);
  }
  #undef lc
  #undef rc
  #undef mid
} sgtMax;

struct SAM{
  static const int N = 6e5 + 10, K = 26, LOGN = 13;
  int len[N], fa[N], lst = 1, tot = 1;
  int ch[N][K], n, id[N], sz[N];
  char s[N];
  vi ed[N];
  struct node {
    //  positive               negitive
    int a[2] = {-iinf, -iinf}, b[2] = {iinf, iinf};
    friend node operator+(node a, node b) {
      node c; vi v1, v2;
      v1.pb(a.a[0]), v1.pb(b.a[0]);
      v2.pb(a.b[0]), v2.pb(b.b[0]);
      v1.pb(a.a[1]), v1.pb(b.a[1]);
      v2.pb(a.b[1]), v2.pb(b.b[1]);
      sort(all(v1)), sort(all(v2));
      c.a[0] = v1[3], c.a[1] = v1[2];
      c.b[0] = v2[0], c.b[1] = v2[1];
      return c;
    }
    ll getmax() {
      ll res = -inf;
      if(a[0] != -iinf && a[1] != -iinf) res = max(res, 1ll * a[0] * a[1]);
      if(b[0] != iinf && b[1] != iinf) res = max(res, 1ll * b[0] * b[1]);
      if(a[0] != -iinf && b[0] != iinf) res = max(res, 1ll * a[0] * b[0]);
      return res;
    }
  } f[N];
  void insert(int c) {
    int f = lst, x = lst = ++tot;
    len[x] = len[f] + 1;
    for(; f && !ch[f][c]; f = fa[f]) ch[f][c] = x;
    if(!f) { fa[x] = 1; return; }
    if(len[ch[f][c]] == len[f] + 1) { fa[x] = ch[f][c]; return; }
    int w = ch[f][c], q = ++tot;
    len[q] = len[f] + 1, fa[q] = fa[w], fa[w] = fa[x] = q;
    mcpy(ch[q], ch[w]);
    for(; f && ch[f][c] == w; f = fa[f]) ch[f][c] = q;
  }
  void dfs(int x) {
    for(int y: ed[x]) {
      dfs(y);
      sz[x] += sz[y];
      f[x] = f[x] + f[y];
    }
    sgtSum.update(1, 0, n - 1, len[fa[x]] + 1, len[x], 1ll * sz[x] * (sz[x] - 1) / 2);
    sgtMax.update(1, 0, n - 1, len[fa[x]] + 1, len[x], f[x].getmax());
  }
  void build(const char *_s, int _n) {
    n = _n; memcpy(s + 1, _s + 1, n);
    per(i, n, 1) insert(s[i] - 'a'), id[i] = lst;
    rep(i, 1, tot) ed[fa[i]].pb(i);
    rep(i, 1, n) {
      sz[id[i]]++;
      node tmp;
      if(a[i] > 0) tmp.a[0] = a[i];
      else tmp.b[0] = a[i];
      f[id[i]] = f[id[i]] + tmp;
    }
    len[fa[1]] = -1;
    dfs(1);
  }
} g;

int main() {
  scanf("%d%s", &n, s + 1);
  rep(i, 1, n) scanf("%lld", a + i);
  sgtMax.build(1, 0, n - 1);
  g.build(s, n);
  sgtSum.getall(res1, 1, 0, n - 1);
  sgtMax.getall(res2, 1, 0, n - 1);
  rep(i, 0, n - 1) {
    printf("%lld %lld\n", res1[i], res2[i] == -inf? 0: res2[i]);
  }
}