树状数组套主席树可以类似这样的方法求kth吗,求教
查看原帖
树状数组套主席树可以类似这样的方法求kth吗,求教
531499
windows_fleon楼主2023/7/15 10:00

就像这个求rk

	int query(int now,int l,int r,int L,int R){
		if(!now) return 0;
		if(l>=L&&r<=R) return f[now].sum;
		int ret=0,mid=(l+r)>>1;
		if(L<=mid) ret+=query(f[now].ls,l,mid,L,R);
		if(R>mid) ret+=query(f[now].rs,mid+1,r,L,R);
		return ret;
	}
int query_rk(int l,int r,int k){
	int res=0;
	for(int i=r;i;i-=lowbit(i))
		res+=T[i].query(1,1,tot,1,k-1);
	for(int i=l-1;i;i-=lowbit(i))
		res-=T[i].query(1,1,tot,1,k-1);
	return res+1;
}
2023/7/15 10:00
加载中...