开始线段树合并学傻了直接拿线段树合并莽然后 80pts 滚粗
其实考虑, 如果我们求出了 $ LCP(s_1,s_2) = i $ , 其中 $ s_1,s_2 $ 是后缀, 的权值的和 / 最大值, 做一遍后缀和 / 最大值就好了啊!
这个东西是可以 dp 的! 由于 parent 树本质上是前缀树, parent 树上的 LCA 实际上就是 LCP .
由于权值在前面不好处理, 可以倒过来建前缀树, 也就是建后缀树, 这样权值就在最后一个位置啦
对于一个点来说它作为 LCP 的长度是确定了的 ($ len(x) $) 所以可以直接对于每个点存一下最大值, 最小值(因为有负数),siz 就好了.
其实这个必然可以用 SA 做的, 没有用到后缀自动机的转移, 其实完全可以直接建前缀树. 只用后缀树的话, sa 必然也可以的吧.
不算很难写吧?
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- typedef long long ll;
- #define MAXN 600006
- int n , lst;
- char ch[MAXN]; int w[MAXN];
- ll ans = 0;
- long long tot[MAXN] , res[MAXN];
- struct SAM{
- int son[MAXN][27]; // sons
- int par[MAXN] , len[MAXN]; // node
- int head[MAXN] , nxt[MAXN<<1] , to[MAXN<<1]; // edge
- int cnt , ecnt;
- int sz[MAXN];
- void adde( int u , int v ) {
- to[++ecnt] = v;
- nxt[ecnt] = head[u];
- head[u] = ecnt;
- }
- int mx[MAXN] , semx[MAXN] , mn[MAXN] , semn[MAXN];
- void init( ) {
- memset( son , 0 , sizeof son ) , memset( head , -1 , sizeof head );
- memset( mx , -0x3f , sizeof mx ) , memset( mn , 0x3f , sizeof mn );
- memset( semx , -0x3f , sizeof semx ) , memset( semn , 0x3f , sizeof semn );
- cnt = lst = 1; ecnt = 0;
- }
- void addall( ) { // 将所有 link 边连到边集合中
- for( int i = 2 ; i <= cnt ; ++ i ) adde( par[i] , i );
- }
- void ins( int x , int w ) {
- int cur = ++ cnt;
- len[cur] = len[lst] + 1 , sz[cur] = 1;
- mx[cur] = mn[cur] = w;
- int p = lst;
- while( p && !son[p][x] ) son[p][x] = cur , p = par[p];
- if( !p ) par[cur] = 1;
- else {
- int q = son[p][x];
- if( len[q] == len[p] + 1 ) par[cur] = q;
- else {
- int cl = ++ cnt;
- memcpy( son[cl] , son[q] , sizeof son[q] );
- par[cl] = par[q]; // copy
- len[cl] = len[p] + 1 , par[q] = par[cur] = cl;
- for( ; son[p][x] == q ; p = par[p] ) son[p][x] = cl;
- }
- }
- lst = cur;
- }
- void dfs( int cur ) {
- int l = len[cur];
- for( int i = head[cur] ; ~i ; i = nxt[i] ) {
- int v = to[i];
- dfs( v );
- if( mx[v]> mx[cur] ) semx[cur] = mx[cur] , mx[cur] = mx[v];
- else if( mx[v]> semx[cur] ) semx[cur] = mx[v];
- if( semx[v]> semx[cur] ) semx[cur] = semx[v];
- if( mn[v] <mn[cur] ) semn[cur] = mn[cur] , mn[cur] = mn[v];
- else if( mn[v] < semn[cur] ) semn[cur] = mn[v];
- if( semn[v] < semn[cur] ) semn[cur] = semn[v];
- tot[l] += 1ll * sz[cur] * sz[v];
- sz[cur] += sz[v];
- }
- if( semx[cur]> -1e9 - 10 ) res[l] = max( res[l] , 1ll * mx[cur] * semx[cur] );
- if( semn[cur] <1e9 + 10 ) res[l] = max( res[l] , 1ll * mn[cur] * semn[cur] );
- // printf("%d %d\n",len[cur] , sz[cur]);
- }
- void fuck() {
- puts("fuck");
- }
- } S ;
- int main() {
- S.init();
- cin>> n;
- scanf("%s",ch);
- for( int i = 0 ; i <n ; ++ i ) scanf("%d",&w[i]);
- for( int i = n - 1 ; i>= 0 ; -- i ) S.ins( ch[i] - 'a' , w[i] );
- for( int i = 0 ; i <= n ; ++ i ) res[i] = -1e18;
- S.addall( ) , S.dfs( 1 );
- // S.fuck();
- for( int i = n - 1 ; i>= 0 ; -- i ) tot[i] += tot[i + 1] , res[i] = max( res[i] , res[i + 1] );
- for( int i = 0 ; i < n ; ++ i )
- printf("%lld %lld\n",tot[i],res[i] == -1e18 ? 0 : res[i]);
- }
来源: http://www.bubuko.com/infodetail-3400727.html