abc321E - Complete Binary Tree

E - Complete Binary Tree

首先我们只考虑x子树中的答案，非常明显，一定是一个连续的区间，那么我们只需要找到两个端点即可，左端点一直往左走即可，但是右端点要注意，如果走不了，如果左端点存在，说明n就是我们的右端点。

处理完子树之后往上跳即可，因为树高只有60

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc ( iint(2)*x )
#define rc ( iint(2)*x+iint(1) )
using namespace std;
typedef double db;
typedef long long ll;
typedef __int128 iint;
const int N =1e6+6;
const ll mo=998244353;
const ll inf=1ll<<60;
ll nn,xx,kk;
iint n,x,k,l,r,lx;
void dg(iint x,iint k,int op){
	if (!k) {
		l=min(l,x);
		r=max(r,x);
		return;
	}
	if (!op) {
		if (lc<=n) dg(lc,k-1,op);
	}
	else{
		if (rc<=n) dg(rc,k-1,op);
		else r=n;
	}
}
void solve(){
	ll ans=0;
	n=nn; x=xx; k=kk;
	
	if (!k) {
		printf("%d\n",1);
		return;
	}
	
	l=inf; r=0;
	
	dg(x,k,0);
	dg(x,k,1);

	
	if (l<=r) ans+=r-l+(iint)1;
	lx=x;
	
	x/=(iint)2; k--;
	
	while (x) {
		if (!k) {
			ans++; break;
		}
		l=inf; r=0;
		
		if (lc!=lx && lc<=n) dg(lc,k-1,0),dg(lc,k-1,1);
		if (rc!=lx && rc<=n) dg(rc,k-1,0),dg(rc,k-1,1);
		
		if (l<=r) ans+=r-l+1ll;
		
		k--;
		lx=x;
		x/=2ll;
		
	}
	printf("%lld\n",ans);
}
int main()
{
//	freopen("data.in","r",stdin);
	
	int T;
	scanf("%d",&T);
//	T=1;
	while (T--){
		scanf("%lld %lld %lld",&nn,&xx,&kk);
		solve();
	}
	return 0;
}