codeforces 123 D. String (后缀数组+两次二分得到区间+rmq)

题目链接

题意:定义一个函数F..

For exampe: F(babbabbababbab, babb) = 6. The list of pairs is as follows:

(1, 4), (4, 7), (9, 12)

Its continuous sequences are:

  • (1, 4)

  • (4, 7)

  • (9, 12)

  • (1, 4), (4, 7)

  • (4, 7), (9, 12)

  • (1, 4), (4, 7), (9, 12)

    erfen


erfen
题目描述得很烂..看例子把..大概就是:如果字符串y在字符串x中出现n次,那么F(x,y)=n*(n+1)/2

现在给一个字符串,求所有的F(s,x)的和,x为字符串的所有不相同的子串.

 

思路:由于刚刚写了一个求一个字符串所有不同子串个数的题目...于是就想到了后缀数组...

写完之后观察height[i].如果把height[i]看成底在x轴上的第i个矩形的高的话,n就是一段连续的矩形的长度.

 

然后...暴力会tle 48

题解说单调栈...但是单调栈之后还要线段树or并查集? (by 羊神)

...不会啊orz

最后用了二分+rmp过掉的

大概就是两次二分得到一个矩形的区间,和whust2016 #1的那道题有点像.

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz