/*
思路
倒着考虑问题,将原来的序列反向,反向之后挨着去掉最前面的字符,得到的答案根原来的问题是等价的,要求一个字符串的不同的子串的数目
其实求的就是该字符串所有的后缀的不同的前缀的数量,就是sum{ n - (sa[i]-1) - height[i] }, 对于一个静态不变的字符串,直接用
这个公式求即可,原来的问题是要不断在字符串末尾添加字符,转换之后就是在翻转的字符串前面依次删除字符,删除最前面的字符其实本质上
是删掉了一个当前最长的后缀,删掉这个后缀之后,剩下的后缀还是一个字符串的完整后缀集合,所以删掉后缀之后只要能维护住height数组,
新的height数组就是删掉了头上字符之后剩下那个字符串的height数组,删掉原字符串的第i个后缀,等价于在height数组中将第rk[i]项
删掉了,一开始整个height是有n项的,删掉一个之后,剩下的height数组中有效数据的相对顺序是不变的,所以用一个链表维护住height数组
中剩下的值,假设当前排名rk_j的后缀是排名rk[i]的后缀在链表中的后一个,那删除掉第i个后缀,只会影响到height[rk_j]的数值,
height[rk_j] = min{ height[rk[i]], height[rk_j] }, 这个是后缀数组的性质,所以,删除当前最长的一个前缀,对于height数组
的更新是O(1)可以维护住的,对于sum{ n - (sa[i]-1) - height[i] }的影响就是扣掉排名rk[i]的后缀对应的 n - (sa[rk[i]]-1) - height[rk[i]]
, 再扣掉n - (sa[rk_j]-1) - height[rk_j], 再加上height[rk_j]更新之后的 n - (sa[rk_j]-1) - height[rk_j], 也是O(1)
的代价就可以更新,最后倒着把答案打印一遍
*/
#include <algorithm>
#include <map>
using namespace std;
const int MAX_STR_LEN = 100005;
int input[MAX_STR_LEN];
int xx[MAX_STR_LEN];
int yy[MAX_STR_LEN];
int c[MAX_STR_LEN];
int sa[MAX_STR_LEN];
int rk[MAX_STR_LEN];
int height[MAX_STR_LEN];
long long ans[MAX_STR_LEN];
int ll[MAX_STR_LEN]; // 链表左指针
int rr[MAX_STR_LEN]; // 链表右指针
class SA {
private:
const int* S;
int max_char_val;
bool sa_flag;
bool height_flag;
int str_len;
public:
// 实际计算的时候,为了方便,字符串下标是从1开始的,所以这里S比str错了一位
SA(const int* str, int max_char_val, int n) : S(str-1), max_char_val(max_char_val), sa_flag(false), height_flag(false), str_len(n) { }
int* get_sa() {
int* x = xx;
int* y = yy;
if (sa_flag) {
return sa;
}
int n = str_len, m = max_char_val;
for (int i = 1; i <= n; i ++ )
c[x[i] = S[i]] ++ ;
for (int i = 2; i <= m; i ++ )
c[i] += c[i - 1];
for (int i = n; i; i -- )
sa[c[x[i]] -- ] = i;
for (int k = 1; k <= n; k <<= 1)
{
int num = 0;
for (int i = n - k + 1; i <= n; i ++ )
y[ ++ num] = i;
for (int i = 1; i <= n; i ++ )
if (sa[i] > k)
y[ ++ num] = sa[i] - k;
for (int i = 1; i <= m; i ++ )
c[i] = 0;
for (int i = 1; i <= n; i ++ )
c[x[i]] ++ ;
for (int i = 2; i <= m; i ++ )
c[i] += c[i - 1];
for (int i = n; i; i -- )
sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;
swap(x, y);
x[sa[1]] = 1, num = 1;
for (int 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;
}
for (int i = 1; i <= n; i ++ )
rk[sa[i]] = i;
sa_flag = true;
return sa;
}
int* get_rk() {
if (!sa_flag) {
get_sa();
}
return rk;
}
int* get_height() {
if (height_flag) {
return height;
}
if (!sa_flag) {
get_sa();
}
int n = str_len;
for (int i = 1, k = 0; i <= n; i ++ )
{
if (rk[i] == 1)
continue;
if (k)
k --;
int j = sa[rk[i] - 1];
while (i + k <= n && j + k <= n && S[i + k] == S[j + k])
k ++ ;
height[rk[i]] = k;
}
height_flag = true;
return height;
}
};
map<int, int> hh;
int hash_val = 1;
void add_hash(int val) {
if (hh.find(val) == hh.end()) {
hh[val] = hash_val++;
}
}
int main() {
//freopen("/Users/grh/Programming/CLionProjects/Algorithm/input.txt", "r", stdin);
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &(input[n-1-i]));
add_hash(input[n-1-i]);
}
for (int i = 0; i < n; i++) {
input[i] = hh[input[i]];
}
rr[0] = 1, ll[n+1] = n;
for (int i = 1; i <= n; i++) {
ll[i] = i-1, rr[i] = i+1;
}
SA algo(input, 100005, n);
int* sa_arr = algo.get_sa();
int* h_arr = algo.get_height();
int* rk_arr = algo.get_rk();
long long tot = 0;
for (int i = 1; i <= n; i++) {
tot += n - (sa[i] - 1) - h_arr[i];
}
ans[n-1] = tot;
for (int i = 1; i<= n-1; i++) {
// 将第i个后缀删掉
int rk_i = rk_arr[i];
int rk_j = rr[rk_i];
tot -= n - (sa_arr[rk_i] - 1) - h_arr[rk_i];
tot -= n - (sa_arr[rk_j] - 1) - h_arr[rk_j];
h_arr[rk_j] = min(h_arr[rk_j], h_arr[rk_i]);
tot += n - (sa_arr[rk_j] - 1) - h_arr[rk_j];
ans[n-1-i] = tot;
rr[ll[rk_i]] = rr[rk_i];
ll[rr[rk_i]] = ll[rk_i];
ll[rk_i] = rr[rk_i] = 0;
}
for (int i = 0; i < n; i++) {
printf("%lld\n", ans[i]);
}
return 0;
}