题意：查询区间中位数
思路：模板题，相当于区间第K大的数，主席树可以水过，但划分树是正解。但还没搞明白划分树，先上模板
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 #include <cstdlib> 6 #include <string> 7 #include <vector> 8 #include <algorithm> 9 #include <set> 10 #define repu(i,a,b) for(int i=a;i<b;i++) 11 using namespace std; 12 #define N 1000010 13 #define ll long long 14 #define _cle(m, a) memset(m, a, sizeof(m)) 15 const int MAXN = 100010; 16 const int M = MAXN * 30; 17 int n,q,m,tot; 18 int a[MAXN], t[MAXN]; 19 int T[MAXN], lson[M], rson[M], c[M]; 20 void Init_Hash() 21 { 22 for(int i = 1; i <= n; i++) 23 t[i] = a[i]; 24 sort(t+1,t+1+n); 25 m = unique(t+1,t+1+n) -t-1; 26 } 27 int build(int l, int r) 28 { 29 int root = tot++; 30 c[root] = 0; 31 if(l != r) 32 { 33 int mid = (l+r)>>1; 34 lson[root] = build(l,mid); 35 rson[root] = build(mid+1,r); 36 } 37 return root; 38 } 39 int Hash(int x) 40 { 41 return lower_bound(t+1,t+1+m,x) - t; 42 } 43 int update(int root, int pos, int val) 44 { 45 int newroot = tot++, tmp = newroot; 46 c[newroot] = c[root] + val; 47 int l = 1, r = m; 48 while(l < r) 49 { 50 int mid = (l+r)>>1; 51 if(pos <= mid) 52 { 53 lson[newroot] = tot++; 54 rson[newroot] = rson[root]; 55 newroot = lson[newroot]; 56 root = lson[root]; 57 r = mid; 58 } 59 else 60 { 61 rson[newroot] = tot++; 62 lson[newroot] = lson[root]; 63 newroot = rson[newroot]; 64 root = rson[root]; 65 l = mid+1; 66 } 67 c[newroot] = c[root] + val; 68 } 69 return tmp; 70 } 71 int query(int left_root, int right_root, int k) 72 { 73 int l = 1, r = m; 74 while( l < r) 75 { 76 int mid = (l+r)>>1; 77 if(c[lson[left_root]] -c[lson[right_root]] >= k ) 78 { 79 r = mid; 80 left_root = lson[left_root]; 81 right_root = lson[right_root]; 82 } 83 else 84 { 85 l = mid + 1; 86 k -= c[lson[left_root]] - c[lson[right_root]]; 87 left_root = rson[left_root]; 88 right_root = rson[right_root]; 89 } 90 } 91 return l; 92 } 93 int main() 94 { 95 //freopen("in.txt","r", stdin); 96 //freopen("out.txt","w", stdout); 97 int kase = 1; 98 while(scanf("%d",&n) == 1) 99 { 100 tot = 0; 101 for(int i = 1; i <= n; i++) 102 scanf("%d",&a[i]); 103 Init_Hash(); 104 T[n+1] = build(1,m); 105 for(int i = n; i ; i--) 106 { 107 int pos = Hash(a[i]); 108 T[i] = update(T[i+1],pos,1); 109 } 110 printf("Case %d: ",kase++); 111 scanf("%d",&q); 112 while(q--) 113 { 114 int l,r,k; 115 scanf("%d%d",&l,&r); 116 k = (r-l)/2+1; 117 printf("%d ",t[query(T[l],T[r+1],k)]); 118 } 119 } 120 return 0; 121 }
先上KB模板
1 //划分树 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int MAXN=100010; 7 int tree[20][MAXN];//表示每层每个位置的值 8 int sorted[MAXN];//已经排序好的数 9 int toleft[20][MAXN];//toleft[p][i]表示第i层从1到i有数分入左边 10 void build(int l,int r,int dep){ 11 if(l==r)return; 12 int mid=(l+r)>>1; 13 int same=mid-l+1;//表示等于中间值而且被分入左边的个数 14 for(int i=l;i<=r;i++)//注意是l,不是one 15 if(tree[dep][i]<sorted[mid]) same--; 16 int lpos=l; 17 int rpos=mid+1; 18 for(int i=l;i<=r;i++){ 19 if(tree[dep][i]<sorted[mid]) tree[dep+1][lpos++]=tree[dep][i]; 20 else if(tree[dep][i]==sorted[mid]&&same>0){ 21 tree[dep+1][lpos++]=tree[dep][i]; 22 same--; 23 } 24 else tree[dep+1][rpos++]=tree[dep][i]; 25 toleft[dep][i]=toleft[dep][l-1]+lpos-l; 26 } 27 build(l,mid,dep+1); 28 build(mid+1,r,dep+1); 29 } 30 //查询区间第k大的数,[L,R]是大区间,[l,r]是要查询的小区间 31 int query(int L,int R,int l,int r,int dep,int k){ 32 if(l==r)return tree[dep][l]; 33 int mid=(L+R)>>1; 34 int cnt=toleft[dep][r]-toleft[dep][l-1]; 35 if(cnt>=k){ 36 int newl=L+toleft[dep][l-1]-toleft[dep][L-1];int newr=newl+cnt-1; 37 return query(L,mid,newl,newr,dep+1,k); 38 } 39 else{ 40 int newr=r+toleft[dep][R]-toleft[dep][r],newl=newr-(r-l-cnt); 41 return query(mid+1,R,newl,newr,dep+1,k-cnt); 42 } 43 } 44 int main(){ 45 int n,m,t=0; 46 while(~scanf("%d",&n)){ 47 memset(tree,0,sizeof(tree)); 48 for(int i=1;i<=n;i++){ 49 scanf("%d",&tree[0][i]); 50 sorted[i]=tree[0][i]; 51 } 52 sort(sorted+1,sorted+n+1); 53 build(1,n,0); 54 scanf("%d",&m); 55 printf("Case %d: ",++t); 56 int s,t,k; 57 while(m--){ 58 scanf("%d%d",&s,&t); 59 k=(t-s+2)/2; 60 printf("%d ",query(1,n,s,t,0,k)); 61 } 62 } 63 return 0; 64 }