复杂度证明
1 int getpre(int x,int las,int l,int r,int k)
2 {
3 if(siz[x]-siz[las]==0)return -1;
4 if(l==r)return l;
5 int mid=(l+r)>>1,res=-1;
6 if(k>mid)res=getpre(rc[x],rc[las],mid+1,r,k);
7 if(~res)return res;
8 return getpre(lc[x],lc[las],l,mid,k);
9 }
10 int getsuf(int x,int las,int l,int r,int k)
11 {
12 if(siz[x]-siz[las]==0)return -1;
13 if(l==r)return l;
14 int mid=(l+r)>>1,res=-1;
15 if(k<=mid)res=getsuf(lc[x],lc[las],l,mid,k);
16 if(~res)return res;
17 return getsuf(rc[x],rc[las],mid+1,r,k);
18 }