首页 > 代码库 > [河南省队2012] 找第k小的数
[河南省队2012] 找第k小的数
★★☆ 输入文件：kth.in 输出文件：kth.out 简单对比
时间限制：1 s 内存限制：128 MB
题目描述
看到很短的题目会让人心情愉悦，所以给出一个长度为N的序列A1,A2,A3,...,AN，
现在有M个询问，每个询问都是Ai...Aj中第k小的数等于多少。
- 输入格式
- 第一行两个正整数N，M。
- 第二行N个数，表示序列A1,A2,...,AN。
- 紧着的M行，每行三个正整数i,j,k(k≤j-i+1)，表示
询问Ai...Aj中第k小的数等于多少。
- 输出格式
共输出M行，第i行输出第i个询问的答案。
- 样例输入1：
- 4 3
- 4 1 2 3
- 1 3 1
- 2 4 3
1 4 4
- 样例输出1：
- 1
- 3
- 4
- 样例输入2：
- 5 5
- 4 2 9 9 10
- 1 3 1
- 2 4 3
- 1 4 4
- 3 5 2
- 2 5 2
- 样例输出2：
- 2
- 9
- 9
- 9
- 9
- 注释：
- 询问区间的第k小值并非严格第k小，例如样例2中第4个询问，询问3到5中第2小的数，
- 答案输出9，并不是严格第2小的10。
- 数据范围：
- 在50%的数据中，1<=N<=10000，1<=M<=10000，A[i]<=100000;
- 在100%的数据中，1<=N<=100000,1<=M<=100000,A[i]<=1000000;
- 思路：主席树+权值线段树
- 代码实现：
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int maxn=1e5+10; 5 int n,k,sz,ts; 6 int a,b,c; 7 int s[maxn],hs[maxn],tt[maxn]; 8 struct tree{int s,l,r,mid,lp,rp;}t[maxn<<5]; 9 void build(int l,int r,int k){10 t[k].l=l,t[k].r=r;11 t[k].mid=l+r>>1;12 if(l==r) return;13 t[k].lp=++ts,t[k].rp=++ts;14 build(l,t[k].mid,t[k].lp);15 build(t[k].mid+1,r,t[k].rp);16 }17 void put(int l,int r,int k,int nk,int p){18 t[nk]=(tree){t[k].s+1,t[k].l,t[k].r,t[k].mid};19 if(l==r) return;20 if(p<=t[nk].mid){21 t[nk].lp=++ts,t[nk].rp=t[k].rp;22 put(l,t[nk].mid,t[k].lp,t[nk].lp,p);23 }24 else{25 t[nk].rp=++ts,t[nk].lp=t[k].lp;26 put(t[nk].mid+1,r,t[k].rp,t[nk].rp,p);27 }28 }29 int search(int k,int nk,int v){30 if(t[k].l==t[k].r) return t[k].l;31 int w=t[t[nk].lp].s-t[t[k].lp].s;32 if(v<=w) return search(t[k].lp,t[nk].lp,v);33 else return search(t[k].rp,t[nk].rp,v-w);34 }35 int main(){36 freopen("kth.in","r",stdin);37 freopen("kth.out","w",stdout);38 scanf("%d%d",&n,&k);39 for(int i=1;i<=n;i++){40 scanf("%d",&s[i]);41 hs[i]=s[i];42 }43 sort(hs+1,hs+n+1);44 sz=unique(hs+1,hs+n+1)-hs-1;45 build(1,sz,tt[0]);46 for(int i=1;i<=n;i++){47 int pos=lower_bound(hs+1,hs+sz+1,s[i])-hs;48 tt[i]=++ts;49 put(1,sz,tt[i-1],tt[i],pos);50 }51 for(int i=1;i<=k;i++){52 scanf("%d%d%d",&a,&b,&c);53 printf("%d\n",hs[search(tt[a-1],tt[b],c)]);54 }55 return 0;56 }
钦定的板子。
题目来源：COGS
[河南省队2012] 找第k小的数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。