学习:http://www.cnblogs.com/pony1993/archive/2012/07/17/2594544.html
划分树的build:
划分树是分层构建的,在构建的t层时,我们可以得到第t层的num域,和分入左右孩子的元素
num域值该区间中从左到某个位置小于指定值的数的个数
查找可以看代码
//Accepted 28504 KB 1422 ms //划分树 #include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <cmath> #include <algorithm> using namespace std; /** * This is a documentation comment block * 如果有一天你坚持不下去了,就想想你为什么走到这儿! * @authr songt */ ; struct node { int val[imax_n]; //val int num[imax_n]; //num long long sum[imax_n]; //sum }f[]; int a[imax_n]; int sorted[imax_n]; void build(int t,int l,int r) { if (l==r) return ; ; ; ; for (int i=l;i<=r;i++) { if (f[t].val[i]<sorted[mid]) isame--; } int ln=l; ; for (int i=l;i<=r;i++) { if (i==l) { f[t].sum[i]=; f[t].num[i]=; } else { f[t].sum[i]=f[t].sum[i-]; f[t].num[i]=f[t].num[i-]; } if (f[t].val[i]<sorted[mid]) { f[t].num[i]++; f[t].sum[i]+=f[t].val[i]; f[t+].val[ln++]=f[t].val[i]; } else if (f[t].val[i]>sorted[mid]) { f[t+].val[rn++]=f[t].val[i]; } else { if (same<isame) { same++; f[t].num[i]++; f[t].sum[i]+=f[t].val[i]; f[t+].val[ln++]=f[t].val[i]; } else { f[t+].val[rn++]=f[t].val[i]; } } } build(t+,l,mid); build(t+,mid+,r); } ; int query(int t,int l,int r,int a,int b,int k) { if (l==r) return f[t].val[l]; int s,ss,b1,b2; ; long long tsum; if (a==l) { s=f[t].num[b]; ss=; tsum=f[t].sum[b]; } else { s=f[t].num[b]-f[t].num[a-]; ss=f[t].num[a-]; tsum=f[t].sum[b]-f[t].sum[a-]; } if (s>=k) //当前查找区间[a,b]里包含的小于t=sorted[(left+right)/2]的数大于k个,则当前区间第k大的数 { //被分到[l,r]的左孩子,区间更新为[left+num[a-1],left+num[b]-1], a=l+ss; //left--a-1 中包含num[a-1]个比t小的数,则[a,b]区间比t小的数,一定在left+num[a-1]后面 b=l+ss+s-;; //left--b 中一共包含了num[b]个比t小的数,则[a,b]区间中比t小的数的最大位置在left+num[b]-1 ,l,mid,a,b,k); } else { //当前查找区间[a,b]中小于t=sorted[(left+right)/2]的数的个数小于k个,则当前区间第k大的数 b1=a-l-ss; //被分到[l,r]的右孩子,区间更新为[mid+1+a-1-left-num[a-1]+1,mid+1+b-left-sum[b]] b2=b-a+-s; //即[mid+1+a-left-num[a-1],mid+1+b-left-sum[b]] a=mid+b1+; //因为left--a-1 分入左孩子的个数为num[a-1],所以分入右孩子的个数为r1=a-1-left+1-num[a-1] b=mid+b1+b2; //映射在右区间的开始位置是:mid+1+r1-1=mid+1+a-left-num[a-1] sum+=tsum; //left--b 分入左孩子的个数为num[b] ,分入右孩子的个数就是b-left+1-num[b] ,mid+,r,a,b,k-s); //映射到右区间得:mid+1+b-left+1-num[b]-1=mid+1+b-left-num[b] } } int n,m; int x,y,k; void slove() { build(,,n); ;i<=m;i++) { scanf("%d%d%d",&x,&y,&k); ,,n,x,y,k); printf("%d\n",t); } } int main() { while (scanf("%d%d",&n,&m)!=EOF) { ;i<=n;i++) { scanf("%d",&a[i]); f[].val[i]=sorted[i]=a[i]; } sort(sorted+,sorted+n+); slove(); } ; }