THE函数式线段树代码怎么写-创新互联
这篇文章主要讲解了“THE函数式线段树代码怎么写”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“THE函数式线段树代码怎么写”吧！
THE函数式线段树代码：
#include#include #include #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#include #include #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函数式线段树代码怎么写这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是创新互联网站建设公司，，小编将为大家推送更多相关知识点的文章，欢迎关注！
当前名称：THE函数式线段树代码怎么写-创新互联
网页路径：http://pwwzsj.com/article/cchppc.html
