題目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1175

?

注意一個很明顯的結論：求區間[p,q]的第K大就等于求區間[p,q]的第q-p+1-k小。

#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h>using namespace std; const int N = 100005;int sorted[N]; int Tree[20][N]; int toLeft[20][N];void Build(int k,int l,int r) {if(l==r) return;int mid=(l+r)>>1;int i,t;t=mid-l+1;for(i=l;i<=r;i++)if(Tree[k][i]<sorted[mid])t--;int L=l;int R=mid+1;for(i=l;i<=r;i++){if(i==l)toLeft[k][i]=0;elsetoLeft[k][i]=toLeft[k][i-1];if(Tree[k][i]<sorted[mid]){toLeft[k][i]++;Tree[k+1][L++]=Tree[k][i];}else if(Tree[k][i]>sorted[mid]){Tree[k+1][R++]=Tree[k][i];}else{if(t!=0){t--;toLeft[k][i]++;Tree[k+1][L++]=Tree[k][i];}elseTree[k+1][R++]=Tree[k][i];}}Build(k+1,l,mid);Build(k+1,mid+1,r); }int Query(int k,int l,int r,int p,int q,int t) {if(p==q) return Tree[k][p];int s,ss;int mid=(l+r)>>1;if(l==p){s=0;ss=toLeft[k][q];}else{s=toLeft[k][p-1];ss=toLeft[k][q]-s;}int L,R;if(t<=ss){L=l+s;R=l+s+ss-1;return Query(k+1,l,mid,L,R,t);}else{L=mid-l+1+p-s;R=mid-l+1+q-s-ss;return Query(k+1,mid+1,r,L,R,t-ss);} }int main() {int n,m,i,j;while(~scanf("%d",&n)){for(i=1;i<=n;i++){scanf("%d",&Tree[0][i]);sorted[i]=Tree[0][i];}std::sort(sorted+1,sorted+n+1);Build(0,1,n);scanf("%d",&m);int p,q,k;while(m--){scanf("%d%d%d",&p,&q,&k);p++;q++;k--;printf("%d\n",Query(0,1,n,p,q,q-p+1-k));}}return 0; }

?

總結

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

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