增强型LCP

增强型LCP

Time Limit:10000MS  Memory Limit:165536K
Total Submit:21 Accepted:3 
Case Time Limit:1000MS

Description

 

Input

 

Output

对于每个Lcp(a,b)操作输出最长公共前缀

Sample Input

47 abab L 13 A 1 ab L 1 3 C 56 cb L 1 3 D 1 2 L 1 3

Sample Output

2 4 2 0

Source

看这个规模和时限Splay维护Hash值显然不靠谱。。
关键是修改操作很少。。于是我们平衡一下。。
那么就用块状链表吧。对每个块维护一个hash数组。
假设长度为N,分成S快。。那么可以在O(S+Log(N/S))的时间求出Lcp。。。
同时修改是O(N/S)的。。。
由于修改很少。。把S改的很小就可以让效率大幅提高。。。
由于本人代码能力太差。。就不写了T_T。。。
开哥就是用块链A的。。Orz啊!!!!!!

6 thoughts on “增强型LCP

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>