静态主席树总结(静态区间的ｋ大)

首先我们先来看一道题

给定N个正整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。       输入格式：
第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。
第二行包含N个正整数，表示这个序列各项的数字。
接下来M行每行包含三个整数 l, r, kl,r,k , 表示查询区间[l, r][l,r]         内的第k小值。
输出格式：
输出包含k行，每行1个正整数，依次表示每一次查询的结果

对于100%的数据满足：\(1 \leq N, M \leq 2\cdot 10^5\) \(1≤N,M≤2⋅10^5\)
对于数列中的所有数\(a_i\),都有\(-10^9\leq a_i\leq 10^9\)

基本思路

这个题目看上去很像一道线段树或者树状数组之类的裸题，但是仔细想想，区间第\(k\)小是线段树等数据结构维护不了的，这个时候，我们就需要引进一种新的数据结构，就是可持久化线段树，也就是主席树。(可持久化数据结构是可以访问历史版本的，这里也可以做到，但是这里不需要访问历史版本，我们只利用可持久化数据结构的思想)
主席树的本质上是N颗值域线段树(不知道值域线段树的请自行转走)，对于每一颗线段树我们都维护从序列开始到这个元素的值域(即第\(i\)颗线段树维护的区间是第一号元素到第\(i\)号元素的值域)。
但实际上我们没有那么多时间和空间去维护\(n\)颗线段树，所以我们就要想，每一颗线段树由于值域相同，它们的形状是完全相同的，并且对于一颗第\(i\)颗线段树来说，它相对于第\(i-1\)颗线段树只增加了一个值，放在值域中，也就只有包含这个值的log个节点不同，所以对于每一颗线段树，我们只需要新开\(log\)个节点,其它的节点就用第\(i-1\)颗线段树的节点(如果你会可持久化数组，就会发现这其实跟可持久化数组很像,准确的说可持续化数组的模型就是主席树)。

注意要离散化
实现过程
---

构建

我们先开一个root数组来保存每一颗线段树的根，对于每一个线段树的节点记录它的值，左儿子和右儿子的编号，在构建第i颗线段树时，我们要同时访问第i-1颗线段树，每次构建一个节点之后，对于不包含这个新增值的儿子我们就直接将第i-1颗线段树的相应的那个儿子作为第i颗线段树的这个儿子。

比如说，假设离散化之后的值域是1~5，第i号元素是1,我们先构建根节点，然后发现这个节点左儿子的值域是1~2,右儿子的值域是3~5，右儿子的值域不包括1,所以右儿子就直接用第i-1颗线段树的右儿子，而此时我们就新建一个节点作为这个节点的左儿子，值为第i-1颗线段树的左儿子的值+1。

    int modify(int l,int r,int x,int k)
    {
        //x表示上一颗线段树当前节点的标号
        //k表示需要新增的元素
        int y=++cnt;//新建当前节点，y位编号
        t[y]=t[x];//将上一颗线段树的节点的信息传递给当前节点
        t[y].x++;/*因为不包含k的节点不会被访问，所以实质上只要被访问过的节点都要加1*/
        if(l==r)return y;
        int mid=(l+r)>>1;
        if(k<=mid)t[y].l=modify(l,mid,t[x].l,k);
        else t[y].r=modify(mid+1,r,t[x].r,k);/*根据k值修改左右儿子信息*/
        return y;//将当前节点的编号号返回上一层
    }

查询

主席树的查询跟值域线段树的查询差不多，值域线段树的查询大家都会吧，我这里就不再赘述，不过，主席树每次需要同时查询两颗线段树，如果我们需要查询\([l,r]\)闭区间中第\(k\)小的值，我们就查询第\(l-1\)颗线段树和第\(r\)颗线段树的信息，由于所有线段树维护的值域完全一样，所以我们可以用第r颗线段树询问到的值减去第\(l-1\)颗线段树的值，就可以得出\([l,r]\)闭区间的值。(注意：你查询到的是离散之后的值，你需要输出的是离散之前的值)

具体实现过程

    int query(int l,int r,int la,int no,int k)
    {
        //la,no,分别表示你要查询的两颗线段树的相应节点编号
        if(l==r)return l;/*如果节点内只有一个值，这就是第k大，直接返回*/
        int l1=t[la].l,l2=t[no].l,r1=t[la].r,r2=t[no].r;
        //l1,r1,l2,r2分别表示这两个节点的左右儿子。
        int s=t[l2].s-t[l1].s  ,  mid=(l+r)>>1;
        if(s>=k)return query(l,mid,l1,l2,k);
        else return query(mid+1,r,r1,r2,k-s);
    }

代码

    #include<bits/stdc++.h>
    using namespace std;
    inline int gi()
    {
        char a=getchar();int b=0;
            while(a<'0'||a>'9')a=getchar();
        while(a>='0'&&a<='9')b=b*10+a-'0',a=getchar();
        return b;
    }
    const int N=1e6+20;
    struct ljq
    {
        int x,id;
    }b[N];
    struct tree
    {
       int l,r,s;
    }t[N*5];
    int cmp(ljq x,ljq y){return x.x<y.x;}
    int a[N],p[N],root[N],n,m,cnt;
    void work1()
    {
        n=gi();m=gi();
        for(int i=1;i<=n;++i)
            b[i].x=gi(),b[i].id=i;
        sort(b+1,b+n+1,cmp);
        b[0].x=-2e9;
        for(int s=0,i=1;i<=n;++i)
        {
            if(b[i].x!=b[i-1].x)p[++s]=b[i].x;
            a[b[i].id]=s;
        }
    }
    void bt(int l,int r,int x)
    {
        if(l==r)return;
        int mid=(l+r)>>1;
        t[x].l=++cnt;
        t[x].r=++cnt;
        bt(l,mid,t[x].l);
        bt(mid+1,r,t[x].r);
    }
    void work2(int l,int r,int la,int no,int x)
    {
        t[no].s=t[la].s+1;
        if(l==r)return;
        int mid=(l+r)>>1;
        t[no].l=t[la].l;
        t[no].r=t[la].r;
        if(x<=mid)
        {
            t[no].l=++cnt;
            work2(l,mid,t[la].l,t[no].l,x);
        }
        else
        {
            t[no].r=++cnt;
            work2(mid+1,r,t[la].r,t[no].r,x);
        }
    }/*这个构建主席树的实现过程和上面略有不同，上面的更方便，是我在打带修改的主席树的时候写的，这里我懒得改了，仅做参考*/
    int query(int l,int r,int la,int no,int k)
    {
        if(l==r)return l;
        int l1=t[la].l,l2=t[no].l,r1=t[la].r,r2=t[no].r;
        int s=t[l2].s-t[l1].s,mid=(l+r)>>1;
        if(s>=k)return query(l,mid,l1,l2,k);
        else return query(mid+1,r,r1,r2,k-s);
    }
    int main()
    {
        work1();
        root[0]=++cnt;
        bt(1,n,1);
        for(int i=1;i<=n;++i)
        {
            root[i]=++cnt;
            work2(1,n,root[i-1],root[i],a[i]);
        }
        while(m--)
        {
            int l=gi(),r=gi(),k=gi();
            int x=query(1,n,root[l-1],root[r],k);
            printf("%d\n",p[x]);
        }
        return 0;
    }