这篇文章主要讲解了“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函数式线段树代码怎么写这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://www.xuebuyuan.com/3261319.html
