{"id":247,"date":"2010-05-14T12:33:00","date_gmt":"2010-05-14T04:33:00","guid":{"rendered":"http:\/\/localhost\/?p=247"},"modified":"2010-05-14T12:33:00","modified_gmt":"2010-05-14T04:33:00","slug":"rqnoj_find_the_k-th_smallest_number","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=247","title":{"rendered":"RQNOJ \u627e\u7b2ck\u5c0f\u7684\u6570"},"content":{"rendered":"\n

\u54ce\u3002\u3002\u6700\u8fd1\u72b6\u6001\u5f88\u9893\u5e9f\u554a\u3002\u3002\u3002
\u8fd9\u9053\u9898\u9898\u76ee\u7b97\u6cd5\u5730\u7403\u4eba\u90fd\u77e5\u9053\uff0c\u5c31\u662f\u7ebf\u6bb5\u6811+\u4e8c\u5206\u5224\u5b9a\uff0c\u4f46\u6211WA\u4e86N\u6b21\u56e7\u3002\u3002\u3002
\u8bbe\u5f53\u524d\u7684\u533a\u95f4\u662fl,r\u3002\u3002\u90a3\u4e48\u8bbeC(x)\u4e3a\u7528\u7ebf\u6bb5\u6811\u7684\u5728l,r\u4e2d\u5c0f\u4e8ex\u7684\u4e2a\u6570\uff0c\u90a3\u4e48\u5982\u679c\u5f53\u524d\u8981\u7b2ck\u5c0f\u7684\u6570\uff0c
\u5219C(x)=k-1,\u540c\u65f6x\u5c5e\u4e8el\u548cr\u4e4b\u95f4\uff0c\u6240\u4ee5C(x+1)=k\u3002\u3002\u5c31\u662f\u627e\u51fa\u6700\u5927\u7684C(x)\u4e3ak-1\u7684\u6570\u3002\u3002\u3002
Code\uff1a<\/p>\n

#include<cstdio>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=10000+10;#define Left t*2,l,l+r>>1#define Right t*2+1,l+r>>1,rint*T[maxn*4],n,m,A[maxn],d;void Build(int t,int l,int r){ int s=r-l; T[t]=new int[s]; memcpy(T[t],A+l,sizeof(int)*s); sort(T[t],T[t]+s); if(s>1)Build(Left),Build(Right);}int get(int*D,int s,int x){ int i,l; for(i=-1,l=d;l;l>>=1) if(i+l<s&&D[i+l]<x) i+=l; return i+1;}int Count(int t,int l,int r,int a,int b,int x){ if(l>=b||r<=a)return 0; if(l>=a&&r<=b)return get(T[t],r-l,x); return Count(Left,a,b,x)+Count(Right,a,b,x);}#define Cal(x) (Count(1,0,n,a,b,x))int Ask(int a,int b,int k){ int i,l; for(i=n,l=d;l;l>>=1) if(i-l>=0&&Cal(A[i-l])>=k) i-=l; return A[i-1];}int main(){ \/\/freopen("in","r",stdin); scanf("%d%d",&n,&m); rep(i,n)scanf("%d",A+i); Build(1,0,n);sort(A,A+n);A[n]=1e6;int l,r,k; d=1;while(d<=n)d<<=1;d>>=1; while(m–) { scanf("%d%d%d",&l,&r,&k);l–; printf("%dn",Ask(l,r,k)); }} <\/p>\n","protected":false},"excerpt":{"rendered":"

\u54ce\u3002\u3002\u6700\u8fd1\u72b6\u6001\u5f88\u9893\u5e9f\u554a\u3002\u3002\u3002\u8fd9\u9053\u9898\u9898\u76ee\u7b97\u6cd5\u5730\u7403\u4eba\u90fd\u77e5\u9053\uff0c\u5c31\u662f\u7ebf\u6bb5\u6811+\u4e8c\u5206\u5224\u5b9a\uff0c\u4f46\u6211WA\u4e86N\u6b21\u56e7\u3002\u3002\u3002\u8bbe\u5f53\u524d\u7684\u533a\u95f4\u662fl,r\u3002\u3002\u90a3\u4e48\u8bbeC(x)\u4e3a\u7528\u7ebf\u6bb5\u6811\u7684\u5728l,r\u4e2d\u5c0f\u4e8ex\u7684\u4e2a\u6570\uff0c\u90a3\u4e48\u5982\u679c\u5f53\u524d\u8981\u7b2ck\u5c0f\u7684\u6570\uff0c\u5219C(x)=k-1,\u540c\u65f6x\u5c5e\u4e8el\u548cr\u4e4b\u95f4\uff0c\u6240\u4ee5C(x+1)=k\u3002\u3002\u5c31\u662f\u627e\u51fa\u6700\u5927\u7684C(x)\u4e3ak-1\u7684\u6570\u3002\u3002\u3002Code\uff1a #include<cstdio>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=10000+10;#define Left t*2,l,l+r>>1#define Right t*2+1,l+r>>1,rint*T[maxn*4],n,m,A[maxn],d;void Build(int t,int l,int r){ int s=r-l; T[t]=new int[s]; memcpy(T[t],A+l,sizeof(int)*s); sort(T[t],T[t]+s); if(s>1)Build(Left),Build(Right);}int get(int*D,int s,int x){ int i,l; for(i=-1,l=d;l;l>>=1) if(i+l<s&&D[i+l]<x) i+=l; return i+1;}int Count(int t,int l,int r,int a,int b,int x){ if(l>=b||r<=a)return 0; if(l>=a&&r<=b)return get(T[t],r-l,x); return Count(Left,a,b,x)+Count(Right,a,b,x);}#define Cal(x) (Count(1,0,n,a,b,x))int Ask(int a,int b,int k){ int i,l; […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/247"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=247"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/247\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=247"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=247"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=247"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}