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

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

THE函数式线段树代码：

#include #include #include #define lson st[num].ls#define rson st[num].rsusing 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 #include #include #define lson st[num].ls#define rson st[num].rsusing 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函数式线段树代码怎么写这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是，小编将为大家推送更多相关知识点的文章，欢迎关注！