1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 const int MAXN = 100010; 8 int tree[30][MAXN]; //each row has numbers 9 int sorted[MAXN]; 10 int toleft[30][MAXN]; // 表示第i层从1到i有多少个数分入到左边 11 12 void buid(int l,int r,int dep) 13 { 14 if ( l== r) return ; 15 int mid = (l+r)>>1; 16 int same = mid-l+1; //中间值而且被分入左边的个数 17 for (int i = l;i<=r;i++) 18 if (tree[dep][i] < sorted[mid]) 19 same--; 20 int lpos = l; 21 int rpos = mid+1; 22 for (int i = l;i<=r;i++) 23 { 24 if (tree[dep][i] < sorted[mid]) 25 tree[dep+1[lpos++] = tree[dep][i]; 26 else if (tree[dep][i] == sorted[mid] && same > 0) 27 { 28 tree[dep+1][lpos++] = tree[dep][i]; 29 same--; 30 } 31 else 32 tree[dep+1][rpos++] = tree[dep][i]; 33 toleft[dep][i] = toleft[dep][l-1]+lpos-1;//从1到i放到左边的个数 34 } 35 build(l,mid,dep+1); 36 build(mid+1,r,dep+1); 37 } 38 39 int query(int l，int R,int l,int r,int dep,int k) //第K大 传L,R利用L,R进行区间的缩小 40 { 41 if (l == r) return tree[dep][l]; 42 int mid = (L+R) >> 1; 43 int cnt = toleft[dep][r] - toleft[dep][l-1]; // 【l，r】中位于左边的个数 二分的意 44 if(cnt >=k) 45 { 46 // L+要查询的区间被放到左边的个数 47 int newl = L + toleft[dep][l-1] - toleft[dep][L-1]; 48 int newr = newl + cnt -1; 49 return query(L,mid,newl,newr,dep+1,k); 50 } 51 else 52 { 53 int newr = r + toleft[dep][R] - toleft[dep][r]; 54 int newl = newr - (r-l-cnt); 55 return query(mid+1,R,newl,newr,dep+1,k-cnt); 56 } 57 } 58 59 60 int main() 61 { 62 int T; 63 int n,m; 64 int s,t,k; 65 scanf("%d",&T); 66 while (T--) 67 { 68 scanf("%d%d",&n,&m); 69 memset(tree,0,sizeof(tree)); 70 for (int i = 1;i<=n;i++) 71 { 72 scanf("%d",&tree[0][i]); // 将数字放到第一层 然后利用划分 其实是归并 进行建树 73 sorted[i] = tree[0][i]; 74 } 75 sort(sorted+1;sorted+n+1); // sort tree 76 build(1,n,0); 77 while (m--) 78 { 79 scanf("%d%d%d",&s,&t,&k); 80 printf("%d ",query(1,n,s,t,0,k)); 81 } 82 } 83 return 0; 84 }
不保证代码能编译过
上课写的 忘带u盘了