题目大意

对于序列$A$，它的逆序对数定义为满足$i< j$，且$A_i> A_j$的数对$(i,j)$的个数

给$1$到$n$的一个排列，按照某种顺序依次删除$m$个元素，询问在每次删除一个元素之前统计整个序列的逆序对数

阅读更多……

【poj2104】$K-th\ Number$——无修改区间第K小问题

题目大意

给出一个有$n$个数的数列，执行$m$次询问

每次询问在区间$[l,r]$中第$k$小的数

数据范围

$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 5000$

题解

由于操作只有询问，不执行修改，那么可以直接套用可持久化线段树即可

Question Ⅰ：可持久化线段树是啥？

可持久化线段树也叫主席树，它的特点就是能够充分利用历史信息

对于这道题，具体做法就是，建$n$棵权值线段树，第$i$棵树记录在数列区间$[1,i]$中权值出现的个数

然后由于这$n$棵权值线段树的结构都是相似的，所以询问区间$[l,r]$时，可以用第$r$棵权值线段树对应减去第$l-1$棵权值线段树，得到$[l,r]$区间权值的信息，最后沿着新树直接向下查找得到第$k$小的数

Question Ⅱ：建n棵权值线段树，不会空间溢出吗？

直接大力造$n$棵权值线段树肯定会空间溢出啦，但可持久化线段树利用历史信息可以节省大量空间

具体来说，第$i$棵权值线段树和第$i-1$棵权值线段树相比，只是多更新了一个权值

那么这个权值在权值线段树中只是影响了单条路径而已，因此可以在第$i$棵线段树中把不影响的子节点直接指向第$i-1$棵线段树的对应节点，就可以节省好多好多空间啦！

Question Ⅲ：建立权值线段树，那么边界范围不会过大导致自取灭亡吗？

离散化大法好！

阅读更多……