新技能Splay

平衡树这种东西很是玄学，操作倒是十分明了就是不知道为什么这么整能有一个合理的复杂度，至少我已经了解过的Treap和Splay就给我这种感觉。
大概的思想就是通过把访问的节点旋到根节点使得每条路径都多多少少发生些变化，从而防止对同一条很长的路径多次重复访问，复杂度是据说均摊 $log$ 的。

洛谷P3391 - 【模板】文艺平衡树

拿来测板子，但是普通平衡树之前被我用Treap过掉了，就整了个Splay特色。
对区间 $[l,r]$ 翻转可以先把第 $l-1$ 个节点提到根节点，再把第 $r+1$ 个节点提到根节点的右儿子，那么区间 $[l,r]$ 就恰好被包含在第 $r+1$ 个节点的左子树中，对这个子树打一个翻转标记就好了，之后进入这个子树时交换左右儿子即可。

全部评论

推荐最新楼层

05-16 11:13

Fibocom广和通_助理工程师(准入职员工)

5月一大波公司开启了实习

最近又开启很多实习，26届小伙伴抓紧投递！主页置顶文章有获取方式哦，有需要的可以看看。

校招岗位汇总

点赞评论收藏

05-15 22:05

华为_产品经理(准入职员工)

你是我见过最美的牛客女孩

繁华的街道两旁，湿漉漉的下午，两个青涩的脸庞互相张望。宽大卫衣下娇小的她，向我奔来。不约而同的卫衣，斯文的半框眼镜掩饰着一个穷臭屌丝气息。这是我和我牛爱网第一死忠粉兼专属女嘉宾最初的见面。火速恋爱，但是没有所谓的快节奏，相识半年，还是一样的热恋。吃着肉夹馍坐过西安的小三轮洱海边自行车的气球胖吃着她最喜欢的酸酸水果和小乳扇在南山某店爷爷穿孙子衣服，摸肥猫就算我在忙也要抽出时间陪她去吃他喜欢的漂亮饭生活总是平凡，但平凡不平淡还记得见面第一件事儿：“我去上个厕所。”现在早上第一件事儿：“拉*”第一次上我车的她：“我可以坐副驾吗？”现在的她：“老子把jio翘到上面得得挡到你后视镜。”这小孩，虽然花了我...

Stan_蹒跚者：确很厉害，但是有一个小问题：谁问你了？我的意思是，谁在意？我告诉你，根本没人问你，在我们之中0人问了你，我把所有问你的人都请来 party 了，到场人数是0个人，誰问你了？WHO ASKED？谁问汝矣？誰があなたに聞きましたか？누가 물어봤어？我爬上了珠穆朗玛峰也没找到谁问你了，我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒，在找到谁问你之前我连癌症的解药都发明了出来，我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了