bzoj4516

后缀自动机

留个板子

upd:大概懂了 每次新加入的npRight集合肯定只有最后一个位置，那么求所有长得不一样的子串贡献就是Max-Min+1,因为Right集合只有这一个位置，所以这Max-Min+1个子串只出现在最后一个位置。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n;
ll ans;
namespace SAM 
{int root, sz, last;struct node {int par, val;map<int, int> ch;} t[N];int nw(int x) { t[++sz].val = x; return sz; }void iniSAM() { sz = 0; root = last = nw(0); }void extend(int c){int p = last, np = nw(t[p].val + 1);while(p && !t[p].ch[c]) t[p].ch[c] = np, p = t[p].par;if(!p) t[np].par = root;else{int q = t[p].ch[c];if(t[q].val == t[p].val + 1) t[np].par = q;else{int nq = nw(t[p].val + 1);t[nq].ch = t[q].ch;t[nq].par = t[q].par;t[q].par = t[np].par = nq;while(p && t[p].ch[c] == q) t[p].ch[c] = nq, p = t[p].par;}}   ans += t[np].val - t[t[np].par].val;last = np;}
} using namespace SAM;
int main()
{scanf("%d", &n);iniSAM();for(int i = 1; i <= n; ++i) {int x;scanf("%d", &x);extend(x);printf("%lld\n", ans);}return 0;
}