題目：K-th Number

?

如果求區間第K小，就轉換一下就行了，假設你要求區間[u,v]的第k小，那就是第v-u+1-k大

#include<stdio.h> #include<algorithm> #define N 100010int T[N]; int num[N]; int san[N]; int ls[N*20]; int rs[N*20]; int sum[N*20];int tot,rt; int n, m;void Build(int l,int r,int &rt) {rt=++tot;sum[rt]=0;if(l==r) return ;int m=(l+r)>>1;Build(l,m,ls[rt]);Build(m+1,r,rs[rt]); }void Update(int last,int p,int l,int r,int &rt) {rt=++tot;ls[rt]=ls[last];rs[rt]=rs[last];sum[rt]=sum[last]+1;if(l==r) return ;int m=(l+r)>>1;if(p<=m) Update(ls[last],p,l,m,ls[rt]);else Update(rs[last],p,m+1,r,rs[rt]); }int Query(int ss,int tt,int l,int r,int k) {if(l==r) return l;int m=(l+r)>>1;int cnt=sum[ls[tt]]-sum[ls[ss]];if(k<=cnt)return Query(ls[ss],ls[tt],l,m,k);elsereturn Query(rs[ss],rs[tt],m+1,r,k-cnt); }void gogogo() {int l,r,k;for(int i=1;i<=n;i++){scanf("%d",&num[i]);san[i]=num[i];}tot=0;std::sort(san+1,san+n+1);int cnt=std::unique(san+1,san+n+1)-san-1;Build(1,cnt,T[0]);for(int i=1;i<=n;i++) num[i]=std::lower_bound(san+1,san+cnt+1,num[i])-san;for(int i=1;i<=n;i++) Update(T[i-1],num[i],1,cnt,T[i]);while(m--){scanf("%d%d%d",&l,&r,&k);int id=Query(T[l-1],T[r],1,cnt,k);printf("%d\n",san[id]);} }int main() {int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);gogogo();}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU2665(函数式线段树-区间第K大)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。