THE函数式线段树代码怎么写

这篇文章主要讲解了“THE函数式线段树代码怎么写”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“THE函数式线段树代码怎么写”吧！

THE函数式线段树代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson st[num].ls
#define rson st[num].rs
using namespace std;
const int MAXN = 100100;

struct node
{
    int ls,rs,cnt;
};

struct fSTree
{
    node st[MAXN*20];
    int rt[MAXN],cur,rc;

    inline void _pushUp(int num)
    {
        st[num].cnt=st[lson].cnt+st[rson].cnt;
    }

    inline int _build(int l,int r)
    {
        int num=cur++;
        if(l==r)
        {
            st[num].cnt=0;
            return num;
        }
        int m=(l+r)>>1;

        st[num].ls=_build(l,m);
        st[num].rs=_build(m+1,r);
        _pushUp(num);
        return num;
    }

    inline int _insert(int pos,int l,int r,int last)
    {
        int num=cur++;
        st[num]=st[last];

        if(l==r)
        {
            st[num].cnt++;
            return num;
        }

        int m=(l+r)>>1;
        if(pos>m) st[num].rs=_insert(pos,m+1,r,st[num].rs);
        else st[num].ls=_insert(pos,l,m,st[num].ls);
        _pushUp(num);
        return num;
    }

    inline int _quire(int k,int v,int o,int l,int r)
    {
        if(l==r)
            return l;

        int res = st[st[o].ls].cnt - st[st[v].ls].cnt,m=(l+r)>>1;

        if(k<=res)
            return _quire(k,st[v].ls,st[o].ls,l,m);
        else
            return _quire(k-res,st[v].rs,st[o].rs,m+1,r);
    }

    inline void init(int n)
    {
        cur=rc=0;
        rt[rc++]=_build(1,n);
    }

    inline void insert(int n,int pos)
    {
        rt[rc]=_insert(pos,1,n,rt[rc-1]);
        rc++;
    }

    inline int quire(int n,int k,int l,int r)
    {
        return _quire(k,rt[l-1],rt[r],1,n);
    }
}fst;

int hl[MAXN],hs[MAXN];

int main()
{
    //freopen("hdu2665.in","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&hs[i]);
            hl[i]=hs[i];
        }

        sort(hl+1,hl+n+1);
        int nn=unique(hl+1,hl+n+1)-hl-1;
        fst.init(nn);

        for(int i=1;i<=n;i++)
            fst.insert(nn,lower_bound(hl+1,hl+1+nn,hs[i])-hl);

        while(m--)
        {
            int s,t,k;
            scanf("%d%d%d",&s,&t,&k);
            int idx = fst.quire(nn,k,s,t);
            printf("%d\n",hl[idx]);
        }
    }
    return 0;
}

------------------------------------------------

poj 2761
一样的题目啊..结果背板都被击沉一发 -  -

#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson st[num].ls
#define rson st[num].rs
using namespace std;

const int MAXN = 100100;

struct node
{
    int ls,rs,cnt;
};

struct
{
    int rt[MAXN],cur,rc;
    node st[MAXN*20];

    inline void _pushUp(int num)
    {
        st[num].cnt=st[lson].cnt+st[rson].cnt;
    }

    inline int _build(int l,int r)
    {
        int num=cur++,m=(l+r)>>1;

        if(l==r)
        {
            st[num].cnt=0;
            return num;
        }

        st[num].ls=_build(l,m);
        st[num].rs=_build(m+1,r);
        _pushUp(num);
        return num;
    }

    inline int _insert(int pos,int l,int r,int last)
    {
        int num=cur++,m=(l+r)>>1;
        st[num]=st[last];

        if(l==r)
        {
            st[num].cnt++;
            return num;
        }

        if(pos>m)
            st[num].rs=_insert(pos,m+1,r,st[num].rs);
        else
            st[num].ls=_insert(pos,l,m,st[num].ls);
        _pushUp(num);
        return num;
    }

    inline int _quire(int k,int o,int v,int l,int r)
    {
        if(l==r)
            return l;

        int res=st[st[v].ls].cnt-st[st[o].ls].cnt,m=(l+r)>>1;
        if(k<=res)
            return _quire(k,st[o].ls,st[v].ls,l,m);
        else
            return _quire(k-res,st[o].rs,st[v].rs,m+1,r);
    }

    inline void init(int n)
    {
        cur=rc=0;
        rt[rc++]=_build(1,n);
    }

    inline void insert(int n,int pos)
    {
        rt[rc]=_insert(pos,1,n,rt[rc-1]);
        rc++;
    }

    inline int quire(int n,int k,int l,int r)
    {
        return _quire(k,rt[l-1],rt[r],1,n);
    }
}fst;

int hl[MAXN],hs[MAXN];

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&hs[i]);
            hl[i]=hs[i];
        }

        sort(hl+1,hl+n+1);
        int nn=unique(hl+1,hl+n+1)-hl-1;
        fst.init(nn);

        for(int i=1;i<=n;i++)
            fst.insert(nn,lower_bound(hl+1,hl+nn+1,hs[i])-hl);

        while(m--)
        {
            int s,t,k;
            scanf("%d%d%d",&s,&t,&k);
            printf("%d\n",hl[fst.quire(nn,k,s,t)]);
        }
    }
    return 0;
}

感谢各位的阅读，以上就是“THE函数式线段树代码怎么写”的内容了，经过本文的学习后，相信大家对THE函数式线段树代码怎么写这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！