[算法学习] 可持久化线段树基础题 K-th Number

终于要搞可持久化数据结构了

在综合看了了n个大犇的博客和clj的论文之后总算是写了第一道可持久化线段树的题目。话说SCU真的很严格，这个代码在其他地方都过了就是在SCU上TLE。。。所以这个更快版本的今天先放着以后搞出来再说。。。

其实思路倒也不是很复杂，首先说求[1,n]的第k大。

求[1,n]的第k大就是按照离散化后按照权值组成线段树（也就是按照从小到大的顺序），每个节点k保存一下值域[l,r]里现在有多少个点，记为cnt[k]，按照输入顺序一个一个往里加（线段树本身似乎没有插入操作所以这里是先把所有的置为0再修改），然后插入n个之后就很容易找第k小了：因为线段树是按照有序排列的，所以只需要递归的考虑k是不是大于cnt[lchild],如果不大于那么肯定在左边，大于肯定在右边，注意王右边转移的时候要变成k-cnt[lchild]

然后再说求[i,j]的第k大，这里用可持久化结构的话，是每次插入一个新数就多一个版本。这里clj的论文里提到如果写可持久化线段树的话，在两个不同版本树结构相同的情况下，树a-数b的结果就是对应的每个节点的值相减的结果，换句话说，就是在(a,b]中的那些值组成的跟原树同结构的树。那么这时候就是说只需要来个相减操作，其他的都像求[1,n]中第k小一样递归操作就可以了

需要注意的小细节是离散化的前后处理和数组的大小。好吧也不算什么细节只是因为我在这里出错了TAT。另外一个就是如果用数组表示树，可持久化的结构是和普通的线段树不一样的，左右孩子也需要数组，而不是那种l=o*2,r=o*2+1的完全二叉树关系，需要用idx存储当前的总结点数（感觉有点像Trie的数组写法啊

#include 
#include 
#include 
#include 
using namespace std;
const int maxn=2000000+1;

int lc[maxn],rc[maxn],rt[100005],ar[100005],ars[100005],idx,cnt[maxn];

void build(int& k,int l,int r)//make it all 0
{
    k=++idx;//all is idx ,like trie
    if(l==r)
    {
        cnt[k]=0;
        return ;
    }
    else
    {
        int mid=(l+r)>>1;
        build(lc[k],l,mid);
        build(rc[k],mid+1,r);
        cnt[k]=0;
        return ;
    }
}

void change(int old,int &k,int l,int r,int p,int x)
{
    k=++idx;
    lc[k]=lc[old],rc[k]=rc[old],cnt[k]=cnt[old]+1;
    if(l==p&&r==p)
    {
        return ;
    }
    else
    {
        int mid=(l+r)>>1;
        if(p<=mid)change(lc[old],lc[k],l,mid,p,x);
        else change(rc[old],rc[k],mid+1,r,p,x);
        return ;
    }
}


int query(int ov,int nv,int l,int r,int kth)
{
    if(l==r)return l;//when find the kth small
    int mid=(l+r)>>1;
    int res=cnt[lc[nv]]-cnt[lc[ov]];//not cnt[nv]-cnt[ov]!
    if(kth<=res)query(lc[ov],lc[nv],l,mid,kth);
    else query(rc[ov],rc[nv],mid+1,r,kth-res);//+1?
}

int main()
{
    int n,m;
    int T;
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    while (~scanf("%d%d",&n,&m))
    {
        idx=0;
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&ar[i]);
            ars[i]=ar[i];
        }
        sort(ars+1,ars+1+n);
        int ct=1;
        for (int i=2;i<=n;i++)//delete the the repeated ones!
        {
            if(ars[ct]!=ars[i])
                ars[++ct]=ars[i];
        }
        build(rt[0],1,ct);//ct delete the repeated
        for (int i=1;i<=n;i++)
        {
            //cout<