QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 4986. 普勒亚

Statistics

魔法少女小七得到了一个神奇的长度为 $n$ 的字符串 $s$,每个位置对应有一个魔法值 $a_i$。每次她可以使用一个长度为 $l$ 的子串作为咒语。对于长度为 $l$ 的咒语 $t$,它的魔力是它在 $s$ 中出现的每个位置的右端点 $pos_j$ (即$\forall i \in [0,l),\ s_{pos_j-i}=t_{l-i}$)的魔法值 $a_{pos_j}$ 从左往右连成的序列的前缀最大值个数。

对于每个 $i \in [1,n]$,小七想知道 $s$ 中所有长度为 $i$ 的咒语(两个咒语不同当且仅当其对应的字符串内容不同)的魔力之和。你能帮帮她吗?她会给你一个开心魔法作为报酬!

前缀最大值:对于序列$W$来说$W_i$是前缀最大值当且仅当对于任何$j < i$都有$W_j < W_i$。

输入格式

第 $1$ 行,一个长度为 $n$ 的字符串 $s$。

第 $2$ 行,$n$ 个正整数表示对应的魔法值 $a_i$。

输出格式

输出 $1$ 行 $n$ 个正整数,第 $i$ 个数表示长度为 $i$ 的咒语的魔法值之和。

样例数据

样例 1 输入

ababa
5 2 3 4 1

样例 1 输出

3 3 2 2 1

样例 1 解释

长度为 $1$ 的子串有 ab 两种,分别构成序列 5 3 12 4,各自的前缀最大值个数为 $1$ 和 $2$。

长度为 $2$ 的子串有 abba 两种,分别构成序列 2 43 1,各自的前缀最大值个数为 $2$ 和 $1$。

长度为 $3$ 的子串有 ababab 两种,构成序列 3 14,各自的前缀最大值个数为 $1$ 和 $1$。

长度为 $4$ 的子串有 ababbaba 两种,构成序列 41 ,各自的前缀最大值个数为 $1$ 和 $1$。

长度为 $5$ 的子串有 ababa 一种,构成序列 1,前缀最大值个数为 $1$。

样例 2 输入

aaaa
3 2 3 4

样例 2 输出

2 3 2 1

子任务

对于 $20\%$ 的数据,保证 $n \leq 100$ 。

对于另外 $20\%$ 的数据,保证 $n\leq 5\,000$。

对于另外 $20\%$ 的数据,保证 $S$ 全部由 a 构成。

对于 $100\%$ 的数据,保证 $n \leq 10^5,\ a_i\le 10^9$ ,保证 $S$ 由小写英文字母组成。