题意：
给出 N 个数 , M 次查询。每次查询 L R 区间中第 K 大的数。
思路：
线段树+二分区间数列
转自:http://blog.sina.com.cn/s/blog_a46ca3520101be63.html
题目意思非常很简单。给十万个数，每次询问一段连续区间的第k大值。询问次数达到5000次。 在线段树中搜索出来的题目，但是很明显，区间需要记录什么信息才可以查询第k大值就很不好想。 最后想到，只有把这一段中的每个数的大小编号记录才能满足要求，那么就是把这一段中的每个数排序，那么存储的空间就变成了nlogn，构树的时间复杂度也是nlogn，线段树支持一个查询。一段中小于等于tmp的数的个数，用二分来完成这个查询。 最后找一段中的第k小数，二分枚举答案查询即可。 复杂度分析，查询的复杂度，一次二分枚举答案，查询时二分区间，找到区间时，二分数列，三次二分，复杂度为m*loginf*log100000*log100000 大概在5000万左右的复杂度，建树的复杂度大概在200万，所以总的时间复杂度在5000万左右。20s的题目，这个复杂度是可以满足的。
注意：
原文作者提供的思路是：在找到区间时，求一段中小于等于tmp的数的个数，是用二分来完成的，所以不会TLE。
#include <iostream> #include <stdio.h> #include <string.h> #define ls t<<1 #define rs t<<1|1 #define midt (tr[t].l+tr[t].r)>>1 using namespace std; const int maxn=111111; int a[maxn]; int d[maxn*20],lon; const int inf=1111111111; struct { int l,r; int ll,rr; }tr[maxn*4]; int maketree(int t,int l,int r) { tr[t].l=l; tr[t].r=r; if(l==r) { d[++lon]=a[l]; tr[t].ll=lon; tr[t].rr=lon; return(0); } int mid=midt; maketree(ls,l,mid); maketree(rs,mid+1,r); tr[t].ll=lon+1; int l1=tr[ls].ll,r1=tr[ls].rr; int l2=tr[rs].ll,r2=tr[rs].rr; while(l1<=r1&&l2<=r2) { if(d[l1]<d[l2]) d[++lon]=d[l1++]; else d[++lon]=d[l2++]; } while(l1<=r1) d[++lon]=d[l1++]; while(l2<=r2) d[++lon]=d[l2++]; tr[t].rr=lon; } int query(int l,int r,int tmp) { if(tmp>=d[r]) return(r-l+1); if(tmp<d[l]) return(0); int ll=l,rr=r; while(ll<rr) { int mid=(ll+rr)>>1; if(d[mid]>tmp) rr=mid; else ll=mid+1; } return(ll-l); } int query(int t,int l,int r,int tmp) { if(l<=tr[t].l&&r>=tr[t].r) { return(query(tr[t].ll,tr[t].rr,tmp)); } int mid=midt,ret=0; if(l<=mid) ret+=query(ls,l,r,tmp); if(mid+1<=r) ret+=query(rs,l,r,tmp); return(ret); } int main() { int n,k; scanf("%d %d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); maketree(1,1,n); int l,r,tmp; for(int i=1;i<=k;i++) { int l,r,tmp; scanf("%d %d %d",&l,&r,&tmp); int sm=-inf,bg=inf; while(sm<bg) { int mid=(sm+bg)>>1; int t1=query(1,l,r,mid); if(t1<tmp) sm=mid+1; else bg=mid; } printf("%d\n",sm); } return 0; } 在线主席树： #include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <cstring> using namespace std; #define ls l,mid #define rs mid+1,r #define mi (l+r)/2 const int MAXN=1e5+7; vector <int> a; typedef struct Node{ int val; int son[2]; }Node; Node tree[MAXN*20]; int b[MAXN]; int cnt,pos,rtid[MAXN],ans; int new_node(){ int rt=++cnt; tree[rt].val=0; tree[rt].son[0]=tree[rt].son[1]=0; return rt; } int build(int l,int r){ int rt=new_node(); if(l==r){ return rt; } int mid=mi; tree[rt].son[0]=build(ls); tree[rt].son[1]=build(rs); return rt; } void update(int l,int r,int rt,int lart){ tree[rt].val=tree[lart].val; tree[rt].val++; if(l==r) return ; int mid=mi; if(pos>mid){ tree[rt].son[0]=tree[lart].son[0]; tree[rt].son[1]=new_node(); update(mid+1,r,tree[rt].son[1],tree[lart].son[1]); }else{ tree[rt].son[1]=tree[lart].son[1]; tree[rt].son[0]=new_node(); update(l,mid,tree[rt].son[0],tree[lart].son[0]); } } int query(int l,int r,int rt,int lart,int k){ if(l==r) return l; int mid=mi; int sum=tree[tree[rt].son[0]].val-tree[tree[lart].son[0]].val; if(sum>=k) return query(ls,tree[rt].son[0],tree[lart].son[0],k); else return query(rs,tree[rt].son[1],tree[lart].son[1],k-sum); } void ini(){ a.clear();cnt=0; } int main() { int n,m,x,st,en,k,T; while(scanf("%d%d",&n,&m)!=-1){ ini(); for(int i=1;i<=n;i++) scanf("%d",&b[i]),a.push_back(b[i]); sort(a.begin(),a.end());a.erase(unique(a.begin(),a.end()),a.end()); int len=a.size(); rtid[0]=build(1,len); for(int i=1;i<=n;i++){ pos=lower_bound(a.begin(),a.end(),b[i])-a.begin()+1; rtid[i]=++cnt; update(1,len,rtid[i],rtid[i-1]); } for(int i=1;i<=m;i++){ scanf("%d%d%d",&st,&en,&k); ans=query(1,len,rtid[en],rtid[st-1],k); printf("%d\n",a[ans-1]); } } }
Splay：
并归树：
由线段树改编
利用STL给出的 merge 每次并归即可 时间 O（nlognlognlogn）空间 O（nlogn）
#include <iostream> #include <vector> #include <cstdio> #include <algorithm> using namespace std; #define ls l,mid,rt*2 #define rs mid+1,r,rt*2+1 #define sf l,r,rt #define mi (l+r)/2 const int MAXN=1e5+100; const int INF=0x3f3f3f3f; vector <int> tree[MAXN*4],v; int x,n,m,ppp; int a[MAXN]; int st,en,k; int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}//................多加了一步离散化，实际上不需要。 void push_up(int l,int r,int rt){ tree[rt].resize(r-l+1); merge(tree[rt*2].begin(),tree[rt*2].end(),tree[rt*2+1].begin(),tree[rt*2+1].end(),tree[rt].begin());//.....STL } void build(int l,int r,int rt){ if(l==r){tree[rt].clear();tree[rt].push_back(getid(a[++ppp]));return ;} int mid=mi; build(ls); build(rs); push_up(sf); return ; } int queryK(int l,int r,int rt,int v){ if(r<st||l>en) return 0; if(st<=l&&r<=en){ return upper_bound(tree[rt].begin(),tree[rt].end(),v)-tree[rt].begin(); } int mid=mi; int ans=0; ans+=queryK(ls,v); ans+=queryK(rs,v); return ans; } void solve(){//....................二分枚举,虽然会枚举到区间中不存在的数，但枚举结束后一定会枚举到正确的数 int l=0; int r=n; int mid; while(l<r){ mid=mi; if(queryK(1,n,1,mid)>=k){ r=mid; }else{ l=mid+1; } } printf("%d\n",v[l-1]); } int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++)scanf("%d",&a[i]),v.push_back(a[i]); sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end()); ppp=-1;build(1,n,1); while(m--){ scanf("%d%d%d",&st,&en,&k); solve(); } }划分树：
