NOIP 2017系列解题报告 – [题组/NOIP]


Day2 T3 列队 平衡树

题目传送门(LOJ)

题解

分析数据范围,对于一个这么大的数据范围,我们是用啥都存不下的。

发现 Q 比较小,考虑从 Q 入手。

我们可以对每一行的前 m-1 个开共 n 棵平衡树,再对最后一列开一棵平衡树。

  • 对于前 n 棵平衡树,初始都只有一个点 储存三个变量 : siz\;l\;r 代表这个节点表示从 lr 这段数
  • 对于最后一棵平衡树,我们直接扔 n 个节点进去 设其编号为 0

对于每个操作 (x, y) 我们把第 0 棵平衡树中排名为 x 的数字弹出,并压入到第 x 棵平衡树末尾,再将 x 这棵平衡树的第 y 个点弹出,压倒第 0 棵的末尾。

对于并非自己成一个点的弹出操作,我们找到它所在的点之后,把点分裂成三个点,

分别是 [l, x), [x, x+1). [x+1, r) (个人习惯左闭右开)

把要弹出的中间点记录并删除,左点不动,右点重新找个正确的位置插入。

我写的是 Splay 要注意干点什么就 splay 一下

NOIP的数据都水,写个 BST 就可以过90分辣

还有哪里不懂的请看代码~

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注