博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
主席树修正
阅读量:4842 次
发布时间:2019-06-11

本文共 1549 字,大约阅读时间需要 5 分钟。

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #define PAU putchar(' ') 8 #define ENT putchar('\n') 9 #define lson x?x->ch[0]:x,y->ch[0],L,M10 #define rson x?x->ch[1]:x,y->ch[1],M+1,R11 using namespace std;12 const int maxn=10000+10,inf=-1u>>1,maxnode=200000+10;13 struct node{node*ch[2];int siz;node(){siz=0;}}fol[maxnode],*root[maxn],*nodecnt=fol;14 node*ls(node*x){ return x?x->ch[0]:x;}15 node*rs(node*x){ return x?x->ch[1]:x;}16 int sz(node*x){ return x?x->siz:0;}17 int n,Q,A[maxn],num[maxn];18 void build(node*x,node*&y,int L,int R,int pos){19 y=nodecnt++;y->siz=sz(x)+1;if(L==R)return;int M=L+R>>1;20 if(pos<=M) y->ch[1]=rs(x),build(lson,pos);21 else y->ch[0]=ls(x),build(rson,pos);22 }23 int query(node*x,node*&y,int L,int R,int k){24 if(L==R)return L;int M=L+R>>1,kth=sz(ls(y))-sz(ls(x));25 if(k<=kth) return query(lson,k);return query(rson,k-kth);26 }27 int find(int v){28 int L=1,R=n,M;while(L
>1;if(num[M]
=0;i--) putchar(buf[i]+'0');return;40 }41 void init(){42 n=read();Q=read();for(int i=1;i<=n;i++)num[i]=A[i]=read();43 sort(num+1,num+1+n);for(int i=1;i<=n;i++)build(root[i-1],root[i],1,n,find(A[i]));44 return;45 }46 void work(){47 int a,b,c;48 while(Q--){49 a=read();b=read();c=read();50 write(num[query(root[a-1],root[b],1,n,c)]);ENT;51 }52 return;53 }54 void print(){55 return;56 }57 int main(){58 init();work();print();return 0;59 }

 

转载于:https://www.cnblogs.com/chxer/p/4629096.html

你可能感兴趣的文章
将一个数字扁平化,去重并升序
查看>>
边缘缓存模式(Cache-Aside Pattern)
查看>>
博文汇总
查看>>
在Java大环境下.NET程序员如何夺得一线生机
查看>>
GUID做主键真的合适吗
查看>>
【linux之路】常用的命令
查看>>
git将某个分支的代码完全覆盖另一个分支
查看>>
概率DP RED IS GOOD
查看>>
Linux Shell 小脚本经典收藏
查看>>
go tool proof
查看>>
numpy数组及处理:效率对比
查看>>
Luogu P1318 积水面积
查看>>
前台线程 和 后台线程
查看>>
PHP性能优化大全(转)
查看>>
shell编程
查看>>
ImageSwitch+Gallery
查看>>
【软件需求工程与建模 - 小组项目】第0周:团队成员介绍
查看>>
unresolved external symbol "public: virtual __thiscall...错误
查看>>
php连接oracle oracle开启扩展
查看>>
入门自定义标签,(在SSH里面有自定义标签的练习)
查看>>