BZOJ3065 带插入区间K小值

题目传送门

题目大意

带插入、修改的区间k小值在线查询。

题解

调了一下午,最后发现错误如下

正确的:

我写的:

就因为这个

可能还是我太菜了。。

先说一下这题怎么做:

Q1.如何查不带插入的区间第k大?
A:我们可以用普通线段树套值域线段树
Q2.改变一个数的值呢?
A:树状数组套主席树,当然,上面的也行
Q3.那么在数列中插入一个数呢?
很容易想到用平衡树套线段树,但是平衡树是旋转的,而线段树是静态的,一用rotate。。瞬间复杂度爆炸。。
这时候我们可以想到用非旋转的平衡树来维护:
treap非旋转版(本蒟蒻并不会。。),
 朝鲜树(时间复杂度O(sqrt(n)),显然爆炸,学了也没什么用)
替罪羊树(好东西啊!!!!!)
{%vfk大神花式过了此题,但是卡了块状链表:(虽然我不会}
那么对于每一种操作
插入:由于外层平衡树的存在,所以找到这个数字的位置,然后根到其路径上所有节点的权值线段树中插入
修改:和插入差不多,自行YY
查询:直接找到查询区间的若干棵子树,合并成一棵权值线段树,做一下二分。
         (学习hzwer学长暴力合并。。。)
剩下的就是将删去的节点加以利用(因为修改的话是先删除,再插入)
代码如下(丑,勿喷)

 

4 条评论
  1. 不愧是女装大佬

  2. I happen to be commenting to make you understand what a notable encounter my girl gained reading through your blog. She learned too many details, not to mention how it is like to have a marvelous teaching spirit to have other individuals just fully understand various advanced topics. You undoubtedly did more than visitors’ expectations. Many thanks for coming up with the good, trusted, edifying as well as cool thoughts on your topic to Sandra.

发表一条评论