题目大意：给一个大小为n(1e6)的序列，求区间[L,R]上的排行第k的数(5000次)。
AC通道：http://poj.org/problem?id=2104
方法一：按数值大小直接排序，记下排行第i的原来的位置是id[i]；
排好序之后每次询问从左往右数，如果这个落在[L,R]则k--，k=0时输出...
但这莫不是玄学算法...因为最差复杂度明显是过不了的。
于是这就需要将前缀和思想和线段树处理结合的思想了：
传统题目：给一个序列，询问全局排行第k的元素怎么求？
1.nlogn快排预处理，每次O(1)询问
2.二叉排序树，递归下去如果左边子树个数小于等于k往左边走，否则减去之后往右边走[平衡树中的find_kth()]
硬是要你线段树做怎么办?
3.和平衡树类似的思想，将线段树当做一个桶状的结构，记录这个区间内的元素个数，如果左区间的个数小于等于k往左走，否则往右走。
现在我们询问的是区间[L,R]第k大，再看看上面的线段树求全局的过程，如果我们照样是将线段树当桶用，现在我们希望能随时知道在某个数值区间内[L,R]内的数有多少怎么办?
前缀和！
将统计至第L-1个元素和第R个元素的两棵线段树调出来，设为x,y，那么当前数值区间内处于[L,R]内的元素个数为s[y].sz-s[x].sz，然后步骤和上面也就一样了。
所以我们理想的就是对每前i个建立一颗桶状的线段树，查询的时候就方便了。
问题又来了：怎么建n棵线段树而不会MLE呢?
注意到每次都只是在上一次的基础上往桶中放一个元素，所以有很多节点都不会变，只有从根到最后放下的位置的这一条logn的链上会有变化，所以我们可以充分利用之前的信息。
先完全复制原来的点，加入这点之后更改当前点信息，然后若是要往左边走，再递归下去修改左边节点的信息就好。
百度文库里有个ppt有图有真相，可以看一看：
最后附上代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int in(){ int x=0,f=1;char ch=getchar(); while(ch!=‘-‘ && (ch>‘9‘ || ch<‘0‘)) ch=getchar(); if(ch==‘-‘) f=-1,ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar(); return x*f; } const int maxn=100010; struct Node{ int l,r; int sz; }s[maxn*20]; int n,m,key,cnt; int a[maxn],rk[maxn],id[maxn]; int rt[maxn]; bool cmp(const int &x1,const int &x2){ return a[x1]<a[x2]; } void update(const int &l,const int &r,int &pos){ s[++cnt]=s[pos],pos=cnt,s[pos].sz++; if(l==r) return ; int mid=(l+r)>>1; if(key<=mid) update(l,mid,s[pos].l); else update(mid+1,r,s[pos].r); } int query(const int &l,const int &r,const int &x,const int &y,const int &k){ if(l==r) return l; int mid=(l+r)>>1,sum=s[s[y].l].sz-s[s[x].l].sz; if(k<=sum) return query(l,mid,s[x].l,s[y].l,k); else return query(mid+1,r,s[x].r,s[y].r,k-sum); } int main(){ #ifndef ONLINE_JUDGE freopen("2104.in","r",stdin); freopen("2104.out","w",stdout); #endif n=in();m=in(); for(int i=1;i<=n;i++) a[i]=in(),id[i]=i; sort(id+1,id+1+n,cmp); for(int i=1;i<=n;i++) rk[id[i]]=i; for(int i=1;i<=n;i++){ rt[i]=rt[i-1];key=rk[i]; update(1,n,rt[i]); } int l,r; while(m--){ l=in(),r=in(),key=in(); printf("%d\n",a[id[query(1,n,rt[l-1],rt[r],key)]]); } return 0; }
原文：http://www.cnblogs.com/Robert-Yuan/p/5102318.html
