树状数组套权值线段树

在线算法

时间复杂度：$O(nlognlogV)$

空间复杂度：$O(nlognlogV)$

离散化可以降低一点瓶颈复杂度。

这种做法由于空间复杂度的原因不是很实用，学习一下就好。

我们建立可持久化权值线段树的时候是让每颗线段树维护一个前缀，然后区间只需要相减即可查询。

但是带上修改我们发现每次需要修改$O(n)$棵权值线段树。

然后灵机一动想到树状数组对下标的分类方法：让第$i$棵权值线段树维护$(i-lowbit(i) , i]$的区间，这是非常好实现的。这样每次查询xiu’gai只需要$O(logn)$棵权值线段树。

~~以前对树套树不知道的我完全看不懂~~

线段树套平衡树

在线算法

时间复杂度：$O(nlog^2nlogV)$
空间复杂度 : $O(nlogn)$

极其不推荐（也许初学树套树可以试试。。。）

原理很简单，首先由于这种外层区间线段树内层权值平衡树的结构要求查询区间可以分成子区间查询然后合并答案，但是第$k$大显然是不支持的。

但是我们可以二分。

问题转化为查询区间有多少个比当前值小的值。这是可以利用这种数据结构在$O(log^2n)$的时间里完成的。

时间复杂度就是$O(nlog^2nlogV)$，如果可以离散化就是$O(nlog^3n)$.

权值线段树套区间平衡树

时间复杂度$O(nlognlogV)$

空间复杂度$O(nlogV)$

外层使用一个动态开点的权值线段树，每个权值区间维护一颗区间平衡树。

查询区间第$k$大我们只需要在外层权值线段树上用经典的第$k$大分治，每次在权值区间查询下标区间的复杂度是$O(logn)$，修改可以转化为一次插入一次删除，把原来权值的$O(logn)$棵平衡树删除这个元素，在新权值的$O(nlogn)$棵平衡树插入这个元素。元素的权值是下标，维护平衡树子树大小。

这种做法还是很不错的，不过用的人好像不多。

整体二分

离线算法

时间复杂度:$O(nlog^2n)$

空间复杂度：$O(nlogn)$

应该把操作询问序列按照权值分治。每次修改看成一次插入一次删除，然后扫一遍左边的修改，如果第$p$个位置大于等于当前的二分值，在树状数组的这个位置$p$上加或者减去1（取决于插入还是删除）。然后右边的用树状数组差分查一下区间（下标）里有多少个，然后对$k$分治。

~~（谁都会的东西我还是写的麻烦了点）~~

~~都是想着玩口胡的，不过正确性还是能保证的。~~

神仙WC模拟赛题，感觉挺有意思记一下。

https://www.cnblogs.com/ouuan/p/noiac_WC2019simulation1_T1.html

题目大意

给你一个数列，每次可以任取两个不相交的区间，取一次的贡献是这两个区间里所有数的最小值，求所有取法的贡献和，对 $10^9+7$ 取模。

数列长度 $2×10^5$，值域 $1 … 10^9$。