数据结构好题。学会了平衡树代替权值线段树(雾 题目描述 黑白棋的棋盘有 $N$ 行 $M$ 列,而且这 $N\times M$ 个位置上全部都放好了棋。棋的正面为白色,反面为黑色。我给这个棋盘的每行每列都施展了一...
Treap
洛谷 P3285 / loj 2212 [SCOI2014] 方伯伯的 OJ 题解【平衡树】【线段树】
平衡树分裂钛好玩辣! 题目描述 方伯伯正在做他的 OJ。现在他在处理 OJ 上的用户排名问题。 OJ 上注册了 $ n$ 个用户,编号为 $ 1\sim n$,一开始他们按照编号排名。方伯伯会按照心情对这些用户做...
洛谷 P5021 NOIp2018提高组 赛道修建 题解【二分答案】【贪心】【平衡树】
考场上因为平衡树的细节处理不过关而导致菊花图RE。丢了30分比较可惜。 题目描述 \(\text{C}\)城将要举办一系列的赛车比赛。在比赛前,需要在城内修建\(m\)条赛道。 \(\text{C}\)城一共有\(n\)...
洛谷 P3747 相逢是问候 题解【树状数组】【欧拉定理】【快速幂】【平衡树】
一道充分考察了扩展欧拉定理的题目,并且细节要求比较多。 题目描述 Informatik verbindet dich und mich. 信息将你我连结。 B 君希望以维护一个长度为\(n\)的数组,这个数组...
洛谷 P2042 [NOI2005]维护数列 题解【平衡树】
一道令人闻风丧胆的平衡树题终于过了…… 题目描述 请写一个程序,要求维护一个数列,支持以下 6 种操作:(请注意,格式栏中的下划线'_'表示实际输入文件中的空格) 操作编号 输入文件中...
洛谷 P4883 mzf的考验 题解【平衡树】【二进制】【与或异或】
感觉比较麻烦但是还是比较简单的好题。 题目背景 \(mzf\)立志要成为一个豪杰,当然,他也是一个\(OIer\)。 他希望自己除了会\(OI\)之外还会各种东西,比如心理学、吉他、把妹等等。 为了让自己有...
fhq_treap学习笔记【平衡树】
fhq_treap是一个比较好写,扩展性强,并且可以完成splay所有操作的常数不大的数据结构。 fhq_treap不用旋转,它基于重构,也就是平衡树的合并和分裂。它可以通过一系列操作做到像splay一样...
洛谷P2611/bzoj2658 [ZJOI2012]小蓝的好友 题解【Treap】【补集转换】
只会splay的选手过来打Treap 题目描述 终于到达了这次选拔赛的最后一题,想必你已经厌倦了小蓝和小白的故事,为了回馈各位比赛选手,此题的主角是贯穿这次比赛的关键人物——小蓝的好友。 &nb...