bzoj 1014: [JSOI2008]火星人prefix splay

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1014


好久之前就放到了待刷里面,现在才写=.=

一个点的左子树都是字符串里在它前面的,右子树都是在它后面的。

每个点保存一下:以当前点为根的子树所组成的字符串的哈希值。

查询:二分答案,然后用两次splay把想要查询的区间放到【根节点的右儿子的左儿子】,假设现在要查询区间 $[l,r]$ 的哈希值,先把 $l-1$ 旋转到根,再把 $r+1$ 旋转到根的右儿子。每次判断两段是否相等就可以。

修改:把想要修改的点旋转到根,直接修改,pushup一次就可以了。

插入:第一步操作和查询那个差不多,假设要插到 $pos$ 后面,把根变成 $pos$ ,把根的右儿子变成 $pos+1$ ,然后直接把节点接到 $pos+1$ 的左儿子就可以了。

splay题一发A还是很舒服的o( ̄▽ ̄)ブ

 

发表评论