以前学SAM的时候看到过这道题，但因为当时才疏学浅，就姑且弃疗。如今刷到NOI2015，又遇到了这道题。

既然在刷NOI的题，那首先就应该想暴力。

\(O(n ^ 3)\)的暴力就是枚举长度，再枚举点对，哈希判相同子串。太捞了，不想写。

\(O(n ^ 2)\)也比较好想。我们把枚举点对的过程优化掉。开一个map，相同哈希值的子串存到一块，然后扫一遍的的时候先查跟他哈希值相同的子串有多少个，再把这个子串的哈希值加到map中。

如果直接取模哈希+map，可能会面临这哈希冲突和TLE的风险，果不其然，一交上去只有20分。所以我写了个双哈希+哈希表，就是我们把取模的哈希建成哈希表，然后为了防止冲突，在表里找的是这个子串的自然溢出哈希值。这样就特别稳了。期望得分40分，实际得分50hhhh。

暴力代码会在最后放。

下面开始谈谈正解。

先想第一问。

考虑一个节点的endpos的数量就是这类子串在原串中的出现次数，那么对于一个节点，记他的endpos数量为\(siz\)，那么能匹配的点对就是\(\frac{siz * (siz - 1)}{2}\)。这是长度为\([len[fa] + 1, len[u]]\)的子串能匹配的点对数量，我们把这个长度区间的答案都加上这个值。刚开始我zz的想线段树，想了一会儿发现差分不就得了。

接下来第二问。

如果一个子串能匹配，那么他的子串必定能匹配。对应的就是后缀树上一个点的最优解是他的所有子树中的最优解。而因为有负数，所以我们要维护最大值，次大值，最小值，次小值。然后如果一个点是原串中的一个结束位置，就尝试\(a_{id[i]}\)更新这些值，否则取子树的最优解。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;#define enter puts("") #define space putchar(' ')#define Mem(a, x) memset(a, x, sizeof(a))#define In inlinetypedef long long ll;typedef double db;const ll INF = 1e18; //别忘了答案会爆intconst db eps = 1e-8;const int maxn = 3e5 + 5;In ll read(){ ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans;}In void write(ll x){ if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0');}In void MYFILE(){#ifndef mrclr freopen("ha.in", "r", stdin); freopen("ha.out", "w", stdout);#endif}char s[maxn];int n;ll a[maxn];struct Sam{ int cnt, las; int tra[maxn << 1][27], link[maxn << 1], len[maxn << 1], siz[maxn << 1], id[maxn << 1]; In void insert(int c, int x) { int now = ++cnt, p = las; len[now] = len[las] + 1; siz[now] = 1, id[now] = x; while(~p && !tra[p][c]) tra[p][c] = now, p = link[p]; if(p == -1) link[now] = 0; else { int q = tra[p][c]; if(len[q] == len[p] + 1) link[now] = q; else { int clo = ++cnt; memcpy(tra[clo], tra[q], sizeof(tra[q])); len[clo] = len[p] + 1; link[clo] = link[q], link[q] = link[now] = clo; while(~p && tra[p][c] == q) tra[p][c] = clo, p = link[p]; } } las = now; } int buc[maxn << 1], pos[maxn << 1]; In void sort() { for(int i = 1; i <= cnt; ++i) ++buc[len[i]]; for(int i = 1; i <= cnt; ++i) buc[i] += buc[i - 1]; for(int i = 1; i <= cnt; ++i) pos[buc[len[i]]--] = i; } ll tot[maxn], sum[maxn], Max1[maxn << 1], Max2[maxn << 1], Min1[maxn << 1], Min2[maxn << 1]; In void get_max(int now, ll d) { if(abs(d) == INF) return; if(d > Max1[now]) Max2[now] = Max1[now], Max1[now] = d; else if(d > Max2[now]) Max2[now] = d; } In void get_min(int now, ll d) { if(abs(d) == INF) return; if(d < Min1[now]) Min2[now] = Min1[now], Min1[now] = d; else if(d < Min2[now]) Min2[now] = d; } In void dfs() { for(int i = 0; i <= cnt; ++i) { Max1[i] = Max2[i] = -INF; Min1[i] = Min2[i] = INF; if(i <= n) sum[i] = -INF; } sort(); for(int i = cnt; i; --i) { int now = pos[i], fa = link[now]; if(id[now]) get_max(now, a[id[now]]), get_min(now, a[id[now]]); //刚开始把id[now]写成了now if(siz[now] > 1) { ll tp = 1LL * siz[now] * (siz[now] - 1) / 2; tot[len[fa] + 1] += tp, tot[len[now] + 1] -= tp; sum[len[now]] = max(sum[len[now]], max(Max1[now] * Max2[now], Min1[now] * Min2[now])); } get_max(fa, Max1[now]), get_max(fa, Max2[now]); get_min(fa, Min1[now]), get_min(fa, Min2[now]); siz[fa] += siz[now]; } for(int i = 1; i <= n; ++i) tot[i] += tot[i - 1]; for(int i = n; i; --i) if(tot[i + 1]) sum[i] = max(sum[i], sum[i + 1]); //tot[i] = 0的时候sum[i]不能用来更新答案 write(1LL * n * (n - 1) / 2), space, write(max(Max1[0] * Max2[0], Min1[0] * Min2[0])), enter; for(int i = 1; i < n; ++i) write(tot[i]), space, write(tot[i] ? sum[i] : 0), enter; } In void _Print() { for(int i = 1; i <= cnt; ++i) printf("#%d fa:%d len:%d\n", i, link[i], len[i]); }}S;int main(){ MYFILE(); S.link[0] = -1; n = read(); scanf("%s", s); for(int i = 1; i <= n; ++i) a[i] = read(); reverse(s, s + n); reverse(a + 1, a + n + 1); for(int i = 0; i < n; ++i) S.insert(s[i] - 'a', i + 1); //S._Print(); S.dfs(); return 0;}
              
             
            
           
          
         
        
       
      
     
    

50分暴力

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;#define enter puts("") #define space putchar(' ')#define Mem(a, x) memset(a, x, sizeof(a))#define In inlinetypedef long long ll;typedef unsigned long long ull;typedef double db;const ll INF = 1e18;const db eps = 1e-8;const ll BAS = 233333;const int MOD = 10001707;const ull BAS2 = 19260817;const int maxn = 3e5 + 5;In ll read(){ ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans;}In void write(ll x){ if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0');}In void MYFILE(){#ifndef mrclr freopen("savour.in", "r", stdin); freopen("savour.out", "w", stdout);#endif}int n;char s[maxn];ll a[maxn];#define pr pair
                
                 #define mp make_pairstruct Hash{ int st[maxn], top; int head[MOD], hcnt; int nxt[maxn], w[maxn]; ll Min[maxn], Max[maxn]; ull to[maxn]; In void clear() { while(top) head[st[top--]] = 0; top = hcnt = 0; } In void U(int h, ull h2, ll val) { for(int i = head[h]; i; i = nxt[i]) if(to[i] == h2) { ++w[i]; Min[i] = min(Min[i], val); Max[i] = max(Max[i], val); return; } if(!head[h]) st[++top] = h; ++hcnt; nxt[hcnt] = head[h]; to[hcnt] = h2; w[hcnt] = 1; Min[hcnt] = Max[hcnt] = val; head[h] = hcnt; } In pr Q(int h, ull h2, ll val) { for(int i = head[h]; i; i = nxt[i]) if(to[i] == h2) return mp(w[i], max(val * Min[i], val * Max[i])); return mp(0, 0); }}HA;In ll inc(ll a, ll b) {return a + b < MOD ? a + b : a + b - MOD;}ll has[maxn], p[maxn];ull has2[maxn], p2[maxn];In int H(int L, int R) {return inc(has[R], MOD - has[L - 1] * p[R - L + 1] % MOD);}In ull H2(int L, int R) {return has2[R] - has2[L - 1] * p2[R - L + 1];}In bool solve0(int len){ ll tot = 0, ret = -INF; for(int i = 1; i <= n - len + 1; ++i) { int h = H(i, i + len - 1); ull h2 = H2(i, i + len - 1); pr tp = HA.Q(h, h2, a[i]); if(tp.first) tot += tp.first, ret = max(ret, tp.second); HA.U(h, h2, a[i]); } HA.clear(); write(tot), space, write(tot ? ret : 0), enter; return tot;}In void work0(){ HA.top = HA.hcnt = 0; Mem(HA.head, 0); p[0] = p2[0] = 1; for(int i = 1; i <= n; ++i) { has[i] = (has[i - 1] * BAS + s[i]) % MOD; has2[i] = has2[i - 1] * BAS2 + s[i]; p[i] = p[i - 1] * BAS % MOD; p2[i] = p2[i - 1] * BAS2; } ll Min1 = INF, Min2 = INF, ans0 = -INF; for(int i = 1; i <= n; ++i) { if(a[i] < Min1) Min2 = Min1, Min1 = a[i]; else if(a[i] < Min2) Min2 = a[i]; } ans0 = max(ans0, Min1 * Min2); Min1 = -INF, Min2 = -INF; for(int i = 1; i <= n; ++i) { if(a[i] > Min1) Min2 = Min1, Min1 = a[i]; else if(a[i] > Min2) Min2 = a[i]; } ans0 = max(ans0, Min1 * Min2); write(1LL * n * (n - 1) / 2), space, write(ans0), enter; for(int i = 1; i < n; ++i) if(!solve0(i)) { for(int j = i + 1; j < n; ++j) puts("0 0"); break; }}int main(){ MYFILE(); n = read(); scanf("%s", s + 1); for(int i = 1; i <= n; ++i) a[i] = read(); if(n <= 10000) {work0(); return 0;} work0(); return 0;}