Description

Input

一行,一个字符串S

Output

 

一行,一个整数,表示所求值

Sample Input

cacao

Sample Output


54

HINT

2<=N<=500000,S由小写英文字母组成

学农之前想做的题来着的当时怎么也想不明白现在就好一些了

首先看这个式子的前一部分 由于每个字符串恰好出现了n-1次 所以 答案是

(n-1)*∑len[i]=(n-1)*n*(n+1)/2。 那么显然可以o1求出  那么后面的怎么办 一个显然的方法是暴力枚举o(n^2) 时间复杂度显然难以接受 怎么办 考虑 每个后缀对答案的贡献 每个后缀对答案的贡献一定是这个后缀的height能当最小值的一段区间 大概是前面的个数*后面的个数 那 怎么搞 由于这个顺序并不影响我 我可以单独只考虑height 那么想到 o(n)时间,单调栈求某个点向左能扩展到哪,向右能扩展到哪。两边扩展长度的乘积不就是以该点的值为最小值的区间个数 然后这个最小值乘区间个数就是对答案的贡献 然后最后整体减去这个贡献即可 注意存在height相同的情况 这时候就需要我们更改下判断条件 使得重复的只被计算一次贡献

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论