题目链接

后缀树组解法~

Desprition

每次在字符串末尾添加一个字符，求新字符串的不同子串的个数。

Solution

如果没做过P2408的可以先去康康那道题。

这套题其实就是 \(P2408\) 的加强版，多了一个加操作。

思路转化

因为是用后缀数组做，如果我们每次在末尾添加一个字符，就相当于在改变了每个后缀的基础上再添加了一个新后缀，这样的算法显然是不理想的。

所以我们考虑逆操作，每次要在末尾加，我们就反其道而行之，把它加在开头。这样的话，每次只会多增加一个新后缀而不会对其他后缀造成影响。以此类推，如果我们能将末尾的修改操作转化为在开头的修改操作，就可以达到优化的效果。

那么，在转一转聪明的小脑袋瓜，你会发现：如果我们将序列翻转过来，每次删掉开头的字符，就可以实现逆操作了，是不是很神（\(bai\)）奇（\(chi\)）?

删除操作

继续考虑如何实现删除操作。

首先了解：

所有后缀的前缀的集合就是该字符串的子串集合。

因此，一个后缀对答案造成的影响其实就是他的前缀和，但是需要除去它与它在按字典序排序后的后面一个后缀的最长公共子序列的长度（因为公共的那一部分另一个后缀也出现了，所以不能多减）。

但是我们在操作过程中需要记录当前后缀前面和后面的后缀信息，所以需要用到两个数组 \(u[i]\) 和 \(d[i]\) 记录上下边界的编号。

具体讲解

最后就是具体的删除操作了：

为表示方便，后文将当前要删除的后缀表示为 \(x\) ， \(x\) 的下届表示为 \(y\)。

因为删边造成的影响与 \(x\) 和 \(y\) 有关，然而删除 \(x\) 后， \(y\) 的上界信息也会发生改变，所以可能会造成 \(height_{rk_y}\) 的变化，因此要先将 \(x\) 和 \(y\) 对答案的贡献都删去，继而更新 \(height_{rk_y}\) 的大小，最后再加回 \(y\) 的贡献，更新与 \(x\) 相关的上下界信息。

具体实现看代码，有详细注释的啦~

还有就是因为数据范围太过毒瘤，就得要先离散化哦！

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
#define il inline
const int N = 1e5 + 5;
int n,m,s[N],sa[N],b[N],rk[N],height[N],cnt[N],x[N],y[N],u[N],d[N];
ll ans[N],res;
il void getsa() {//模板 
	int i,k,j,num;
	for(i = 1; i <= n; i ++) cnt[x[i] = s[i]] ++;
	for(i = 2; i <= m; i ++) cnt[i] += cnt[i - 1];
	for(i = n; i; i --) sa[cnt[x[i]]--] = i;
	for(k = 1; k <= n; k <<= 1) {
		num = 0;
		for(i = n - k + 1; i <= n; i ++) y[++num] = i;
		for(i = 1; i <= n; i ++) {
			if(sa[i] > k) y[++num] = sa[i] - k;
		}
		for(i = 1; i <= m; i ++) cnt[i] = 0;
		for(i = 1; i <= n; i ++) cnt[x[i]] ++;
		for(i = 2; i <= m; i ++) cnt[i] += cnt[i - 1];
		for(i = n; i; i --) sa[cnt[x[y[i]]]--] = y[i], y[i] = 0;
		swap(x,y);
		x[sa[1]] = num = 1;
		for(i = 2; i <= n; i ++) {
			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
		}
		if(num == n) break;
		m = num;
	}
} 
il void get_height() {//还是模板
	int i,j,k;
	for(i = 1; i <= n; i ++) rk[sa[i]] = i;
	for(i = 1, k = 0; i <= n; i ++) {
		if(rk[i] == 1) continue;
		if(k) k--;
		j = sa[rk[i] - 1];
		while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++;
		height[rk[i]] = k;
	}
}
il void read(int &x) {
	x = 0;
	char  c = getchar();
	while(c < '0' || c > '9') c = getchar();
	while(c <= '9' && c >= '0') x = x * 10 + c - '0', c = getchar();
} 
il void write(ll x) {
	if(x < 0) {x = -x; putchar('-');};
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
int main() {
	int i,j,k;
	read(n);
	for(i = n; i; i --) read(s[i]), b[i] = s[i];
	sort(b + 1,b + 1 + n);
	m = unique(b + 1,b + 1 + n) - b - 1;
	for(i = n; i; i --) s[i] = lower_bound(b + 1,b + 1 + m,s[i]) - b;//离散化 
	getsa(), get_height();
	for(i = 1; i <= n; i ++) {
		res += n - sa[i] + 1 - height[i];//先算出总值 
		u[i] = i - 1, d[i] = i + 1;//当前后缀的上下界，也就是它上面的后缀编号，和下面的编号 
	}
	d[0] = 1, u[n + 1] = n;//初始化 
	for(i = 1; i <= n; i ++) {//开始删边 
		ans[i] = res;//存值 
		k = rk[i], j = d[k];//删边造成的影响与它自己和它的下届有关。 
		res -= n - sa[k] + 1 - height[k];//减去两个的影响 
		res -= n - sa[j] + 1 - height[j];//
		height[j] = min(height[j],height[k]);//重新给下界的height赋值 
		res += n - sa[j] + 1 - height[j];//记得加回来 
		d[u[k]] = d[k], u[d[k]] = u[k];//因为删除操作，所以当前下届的上届就是当前上届，当前上届的下界就是当前下界 
	}
	for(i = n; i; i --) write(ans[i]),puts("");//反向操作 
	return 0;
}