主席树铺垫——总区间第k小

题目描述（口糊）

先给定一个长度为n的数列，然后给m次操作，每次输入b，求第b小的数。

样例输入

5
7 4 10 9 23
5
1
2
3
4
5

样例输出

4
7
9
10
23

数据范围及温馨提示

1e9 大家一定要用线段树做这道题啊！

建议大家在认真阅读一下逆序对的题解

题解传送门

于是这里我们只需要把query改一下其实就可以了。

int query(int k,int cnt)
{
    if(node[k].l==node[k].r) return node[k].l;
    if(cnt<=node[node[k].son[0]].cnt) return query(node[k].son[0],cnt);
    else return query(node[k].son[1],cnt-node[node[k].son[0]].cnt);
}

其他都一样，我用的是动态开点。

整体代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
struct sd{
    int son[2];
    long long l,r,cnt;
}node[N];
int n;
int cnt=1;
long long ans;
void update(int k)
{
    node[k].cnt=node[node[k].son[0]].cnt+node[node[k].son[1]].cnt;
}
void modify(int k,int val)
{
    if(node[k].l==node[k].r&&node[k].l==val)
    {
        node[k].cnt++;
        return;
    }
    int mid=node[k].l+node[k].r;mid/=2;
    if(node[k].son[0]==0)
    {
        cnt++;
        node[k].son[0]=cnt;
        node[cnt].l=node[k].l;node[cnt].r=mid;
    }
    if(node[k].son[1]==0)
    {
        cnt++;
        node[k].son[1]=cnt;
        node[cnt].l=mid+1;node[cnt].r=node[k].r;
    }
    if(val>mid)
    {
        modify(node[k].son[1],val);
    }
    else
    {
        modify(node[k].son[0],val);
    }
    update(k);
}
/*long long query(int k,int ql,int qr)
{
    if(k==0) return 0;
    if(node[k].l==ql&&node[k].r==qr)
    {
        return node[k].cnt;
    }
    else
    {
        int mid=(node[k].l+node[k].r)/2;
        if(qr<=mid) return query(node[k].son[0],ql,qr);
        else if(ql>mid) return query(node[k].son[1],ql,qr);
        else
        {
            return query(node[k].son[0],ql,mid)+query(node[k].son[1],mid+1,qr);
        }
    }
}*/
long long query(int k,int val)
{
    if(node[k].l==node[k].r) return node[k].l;
    if(val>node[node[k].son[0]].cnt)return query(node[k].son[1],val-node[node[k].son[0]].cnt);
    else query(node[k].son[0],val);
}
int main()
{
    std::ios::sync_with_stdio(false);
    node[1].l=1; node[1].r=1e9+7;
    int n,sth;
    cin>>n;
    ans=0;
    for(int i=1;i<=n;++i)
    {
        cin>>sth;
        modify(1,sth);
    }
    int m;
    cout<<"Please input the number:";
    cin>>m;
    int v;
    for(int i=1;i<=n;++i)
    {
        cin>>v;
        cout<<"The "<<v<<"th max number is:   ";
        cout<<query(1,v)<<endl;
    }
}

总结

其实这个东西可以支持边增加数，边查询第n小，这样总比，加一个数sort一遍要快太多了。然后当你自己已经能够熟练地敲这篇代码的时候，我相信你也很快也可以理解到主席树的精髓！！！