一个初始长度为len的字符串, 一个长度为n的序列a, m个操作:
- 头部插入 在字符串开头添加一个字符 (强制在线)
- 单点修改 令a[x] = pos
- 区间查询 求min{ suffix(a[i]) | l≤i≤r }, 输出i即可; 多解输出最小的i
(1≤n≤5*10^5, 1≤m≤8*10^5, 插入约占1/5, 修改,查询约各占2/5, 保证a[i]合法) 和 [bzoj 3600] 没有人的算术 很像. 想到cls在论文里提到的后缀平衡树......
cls没有具体讲如何快速在线构造, 只是说套用序列顺序问题的解法......大概很显然?
我在想维护每个节点与父亲的lcp神马的......好像不太可行......
遂百度之......TAT
为什么强调后缀平衡树支持头部插入呢? 不仅仅是因为这样只添加了一个后缀, 还因为后缀 = 一个字符 + 另一个后缀. 而原来的后缀两两之间已经可以O(1)比较了.
于是, 就变得和 bzoj3600 一样了.
唉, 不但没能学以致用, 融汇贯通, 还码力低下......写错好几个地方: - 重建后没给节点重新赋值 - 重建没传引用 - double写成int
有点心不在焉......凭印象乱写, 没走心......
代码就不放了, 长得基本一样.
不过, 也发现检验替罪羊树有没有写挂的一个方法: 看最大深度.
建后缀数组的新方法 get