P3369 记录

· · 算法·理论

权值线段树

特点

由于权值线段树需要较小值域，我们需要进行离散化。如何离散化呢？这就是权值线段树的要点：离线算法。什么意思？离线算法，就是先把所有操作读入，进行排序，如此一来，最多 就 10^5 的数据量，时间复杂度 O(Nlog_2N)。每次插入一个数据，我们知道其位置，辣么就很简单了：递归到叶子节点，在返回时 \operatorname{pushup}() 即可。

编码

首先，我们需要两个结构体数组：一个是权值线段树的 \operatorname{t}，另一个是存储每次的操作 \operatorname{actions}。还有一个是用来存储可能在线段树中出现的所有数字：即使它会在将来被删除。

历程

  1. 样例都输出 1，呜呜呜
  2. 经过不懈努力，发现第一个大问题：**初始的
  3. 第二个大问题：我函数名ctrl+C ctrl+V过来时忘了改调用的函数名了！卡了我半个多小时 呜呜呜
  4. 这初始化结构体的玩意不好使啊，大家别用这东西，可能会有杀身之祸 灭族之殃 很大风险，我就是想少写几行代码，用了这个东西，结果废了。。。
  5. 此时提交，得到了 58pts 的(chà)高(píng)分。。。
  6. 在粗糙仔细地检查了代码后，我们发现 \operatorname{rank}() 函数 (对应第三问) 中递归结束，\operatorname{return} 的部分全部返回了 1，但如果递归到这一层时，它是比 \operatorname{max\_value}_i 还大的，辣么返回值不能是 1 了，要变成 2。
  7. 什么分数变成 51pts 了！
  8. 好吧，是我把 \operatorname {size}_u+1 想成 2 了！！！改回了 58pts
  9. 经过思考发现，如果我们求的是某个在数组外的元素的后继，调用 \operatorname{kth\_element} ( \operatorname{rank} ( x ) ) 是正确的；否则需要调用 \operatorname{kth\_element} ( \operatorname{rank} ( x )+1 )。改良后得了 72pts
  10. 理了个发回来发现忘了把前驱改掉了呜呜呜
  11. 诶 前驱怎么改啊 没法改啊 前驱的代码对着呢压
  12. 然后又去看 tj 了
  13. 发现人家也是离线算法，不过将所有的查询节点都记录了。并且递归查找或修改时用在所有 1, 2, 3, 5,6 操作中的值的排名去查找。

正解：Treap(Tree+Heap)

暂无内容

小结

暴力出奇迹，打表切实际

一定要 细心细心再细心啊